Pagini recente » Cod sursa (job #375866) | Cod sursa (job #21586) | Cod sursa (job #1087717) | Cod sursa (job #251950) | Cod sursa (job #2153915)
#include <iostream>
#include <fstream>
#include <cstring>
#define DIM 2000002
using namespace std;
ifstream in ("strmatch.in");
ofstream out("strmatch.out");
int n,m, p[DIM], sol[DIM], nr;
char sir1[DIM], sir2[DIM];
void kmp(){
p[1] = 0;
int l = 0;
for(int i = 2; i <= m; ++ i){
while(sir1[i] != sir1[l + 1] && l != 0)
l = p[l];
if(sir1[i] == sir1[l + 1])
++ l;
p[i] = l;
}
l = 0;
for(int i = 1; i <= n; ++ i){
while(sir2[i] != sir1[l + 1] && l != 0)
l = p[l];
if(sir2[i] == sir1[l + 1])
++ l;
if(l == m){
++ nr;
if(nr <= 1000)
sol[nr] = i - m;
l = p[l];
}
}
}
int main(int argc, const char * argv[]) {
in>>sir1 + 1>>sir2 + 1;
m = strlen(sir1 + 1);
n = strlen(sir2 + 1);
kmp();
out<<nr<<'\n';
nr = min(nr, 1000);
for(int i = 1; i <= nr; ++ i)
out<<sol[i]<<" ";
return 0;
}