Pagini recente » Cod sursa (job #1901037) | Cod sursa (job #1768825) | Cod sursa (job #1600052) | Cod sursa (job #2586518) | Cod sursa (job #2418464)
#include <fstream>
#include <iostream>
#include <cstring>
#define nmax 2000005
using namespace std;
//ifstream fin("date.in");
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[nmax], b[nmax];
int v[nmax], sol[nmax], ok, n, la, lb;
void kmp(){
int i = 0, j = 0;
while(i < lb){
if(b[i] == a[j]){
if(j == (la - 1)){
sol[n++] = i - la + 1;
if(n == 1001)
return;
// ++i;
j = v[j - 1];
}
else{
i++;
j++;
}
}
else{
if(j == 0)
i++;
else
j = v[j - 1];
}
}
}
void prefix(){
int i = 1, j = 0;
while(i < lb){
if(a[i] == a[j]){
v[i] = j + 1;
++i; ++j;
}
else{
ok = 0;
while(ok == 0){
j = v[j - 1];
if(a[i] == a[j]){
v[i] = j + 1;
++i; ++j;
ok = 1;
}
else if(j == 0){
v[i] = 0;
ok = 1;
++i;
}
}
}
}
}
int main(){
fin.getline(a, 20000000);
fin.getline(b, 20000000);
la = strlen(a);
lb = strlen(b);
prefix();
kmp();
fout << n << '\n';
for(int i = 0; i < n; ++i)
fout << sol[i] << " ";
fin.close();
fout.close();
return 0;
}