Pagini recente » Cod sursa (job #3282111) | Cod sursa (job #422237) | Cod sursa (job #2509390) | Cod sursa (job #580712) | Cod sursa (job #2344758)
#include <bits/stdc++.h>
using namespace std;
ifstream inFile("strmatch.in");
ofstream outFile("strmatch.out");
const int NMax = 2000003;
void piFunction(const string &pattern, int pi[]){
pi[0] = -1;
for(int i = 1; i < pattern.size(); ++i){
int k = pi[i - 1];
while(pattern[k + 1] != pattern[i]){
if(k == -1)
break;
k = pi[k];
}
if(pattern[k + 1] != pattern[i]){
pi[i] = -1;
}else{
pi[i] = k + 1;
}
}
}
void KMP(const string &pattern, const string &text, int pi[]){
piFunction(pattern, pi);
int k = -1;
int *piText;
int n = 0;
vector<int> ans;
piText = new int[NMax];
memset(piText, 0, sizeof(piText));
for(int i = 0; i < text.size(); ++i){
if(i == 0){
k = -1;
}else{
k = piText[i - 1];
}
while(pattern[k + 1] != text[i]){
if(k == -1)
break;
k = pi[k];
}
if(pattern[k + 1] != text[i]){
piText[i] = -1;
}else{
piText[i] = k + 1;
if(piText[i] == pattern.size() - 1){
n++;
if(n <= 1000){
ans.push_back(i - pattern.size() + 1);
}
}
}
}
outFile << n << '\n';
for(int i = 0; i < ans.size(); ++i){
outFile << ans[i] << ' ';
}
}
int main(){
string pattern,text;
int *pi;
pi = new int[NMax];
inFile >> pattern;
inFile >> text;
KMP(pattern, text, pi);
return 0;
}