题解分享
题解分享简介
子串 - 题解
直接使用find函数来查找字符串中的字串
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
string c,s;
cin>>s>>c;
int index = 0;
int sum = 0;
while ((index = s.find(c,index)) != string::npos) {
index ++;
sum++;
}
cout << sum << endl;
return 0;
}
```
查看全文
0
0
2
2
子串 - 题解
字符串Hash：O(N) 的复杂度
对主串构造hash前缀，对目标串求hash值。
```
#include <bits/stdc++.h>
using namespace std;
const int base = 131;
const int N = 1e6 + 3;
using ll = long long;
ll h[N], b[N];
ll gethash(int l,int r)
{
return h[r] - h[l-1]*b[r-l+1];
}
int main()
{
string s;
string target;
cin>>s;
cin>>target;
b[0] = 1;
ll key = 0;
for(int i = 0;i<target.length();i++)
{
key = (key*base + target[i] - 'a' + 1);
}
for(int i = 0;i<s.length();i++)
{
h[i+1] = (h[i]*base + s[i] - 'a' + 1);
b[i+1] = b[i]*base;
}
int cnt = 0;
for(int i = 0;i + target.length()<=s.length();i++)
{
if(gethash(i + 1, i + target.length()) == key)
cnt++;
}
cout<<cnt;
}
```
查看全文
0
0
1
2
子串 - 题解
```cpp
// https://dashoj.com/p/74
#include <bits/stdc++.h>
using namespace std;
int main() {
string text, pattren;
cin >> text >> pattren;
string str = pattren + '#' + text;
vector<int> pi(str.size(), 0);
for (int i = 1; i < str.size(); i++) {
int len = pi[i - 1];
while (len != 0 && str[i] != str[len]) len = pi[len - 1];
if (str[i] == str[len]) pi[i] = len + 1;
}
sort(pi.begin(), pi.end(), [](int a, int b) {
return a > b;
});
int cnt = 0, max = pi[0];
for (int i : pi) if (i == max) cnt++; else break;
cout << cnt << endl;
return 0;
}
```
查看全文
0
0
0
4
子串 - 题解
include
using namespace std;
int main(){
string A,B;
getline(cin,A);
getline(cin,B);
long long sum=0;
for(long long i=0;i<A.length();i++){
int pos= A.find(B,i);
if(pos!=string::npos){
sum++;
i=pos;
}
else{
break;
}
}
cout<<sum;
```
return 0;
```
}
查看全文
0
0
0
2
子串 - 题解
kmp算法
```
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
static int next_table[N];
void nexttable(string s, int len) {
int p = 0, i = 1;
next_table[0] = 0;
while (i < len) {
if (s[i] == s[p]) {
p++;
next_table[i] = p;
i++;
}
else {
if (p != 0) {
p = next_table[p-1];
}
else {
next_table[i] = p;
i++;
}
}
}
for (int i = len - 1; i > 0; i--) next_table[i] = next_table[i - 1];
next_table[0] = -1;
}
int kmp(string bigs, string s, int len) {
int count = 0;
int m = bigs.length();
int i = 0, j = 0;
while (j < m) {
if (i == len - 1 && s[i] == bigs[j]) {
count++;
i = next_table[i];
}
if (s[i] == bigs[j]) {
i++; j++;
}
else {
if (next_table[i] == -1) {
j++;
}
else i = next_table[i];
}
}
return count;
}
int main() {
string bigs, s;
cin >> bigs >> s;
int len = s.length();
nexttable(s, len);
cout << kmp(bigs, s, len);
return 0;
}
```
查看全文
0
0
0
3
