Pagini recente » Cod sursa (job #1468437) | Cod sursa (job #3219217) | Cod sursa (job #1592803) | Cod sursa (job #3143879) | Cod sursa (job #1172529)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
#define nmax 2000005
int q, i, j, n, m;
int pi[nmax], sol[nmax];
// Pi[i] = lungimea celui mai lung prefix din P care este si sufix in P
char P[nmax], T[nmax];
void pp(){
pi[1] = 0;
q = 0;
for (i=2; i<=m; i++){
while (q>0 && P[q+1] != P[i]) q = pi[q];
if (P[q+1] == P[i]) q++;
pi[i] = q;
}
}
void kmp(){
pp();
for (i=1, q=0; i<=n; i++){
while (q>0 && P[q+1] != T[i]) q = pi[q];
if (P[q+1] == T[i]) q++;
if (q == m){
sol[++sol[0]] = i - m;
q = pi[q];
}
}
}
int main(){
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> (P+1);
in >> (T+1);
m = strlen(P+1);
n = strlen(T+1);
kmp();
if (sol[0] > 1000) sol[0] = 1000;
out << sol[0] << "\n";
for (i=1; i<=sol[0]; i++)
out << sol[i] << " ";
out << "\n";
return 0;
}