Pagini recente » Cod sursa (job #1231276) | Cod sursa (job #1112883) | Cod sursa (job #1273691) | Cod sursa (job #751348) | Cod sursa (job #1172553)
#include <iostream>
#include <fstream>
#include <cstring>
#define nmax 2000005
using namespace std;
char pattern[nmax];
char text[nmax];
int n, m, i, q;
int pi[nmax], sol[nmax];
void preprocess(){
pi[1] = 0;
q = 0;
for (i=2; i<=m; i++){
while (q>0 && pattern[q+1] != pattern[i]) q = pi[q];
if (pattern[q+1] == pattern[i]) q++;
pi[i] = q;
}
}
void KMP(){
preprocess();
for (i=1, q=0; i<=n; i++){
while (q>0 && pattern[q+1] != text[i]) q = pi[q];
if (pattern[q+1] == text[i])
q++;
if (q == m){
sol[++sol[0]] = i - m;
q = pi[q];
}
}
}
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (pattern + 1);
in >> (text + 1);
n = strlen(text + 1);
m = strlen(pattern + 1);
KMP();
out << sol[0] << "\n";
if (sol[0] > 1000) sol[0] = 1000;
for (i=1; i<=sol[0]; i++)
out << sol[i] << " ";
out << "\n";
return 0;
}