Pagini recente » Cod sursa (job #2943398) | Cod sursa (job #566348) | Cod sursa (job #937200) | Cod sursa (job #2357387) | Cod sursa (job #2480871)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MAXN=2000000;
char a[MAXN],b[MAXN];
int n,m,p[MAXN],c,s[MAXN],nr,cc;
void prefix()
{
for(int i=2; i<=n; i++)
{
while(a[i]!=a[c+1] && c!=0)
c=p[c];
if(a[i]==a[c+1])
c++;
p[i]=c;
}
}
int pi=0;
void kmp()
{ pi=0;
cc=0;
for(int i=1;i<=m;i++)
{ while(b[i]!=a[pi+1] && pi>0)
pi=p[pi];
if(b[i]==a[pi+1])
pi++;
if(pi==n)
{ nr++;
if(pi<=1000)
s[cc++]=i-n;
}
}
}
int main()
{
fin.getline(a+1,MAXN);
fin.getline(b+1,MAXN);
n=strlen(a+1);
m=strlen(b+1);
prefix();
kmp();
fout<<nr<<"\n";
for(int i=0;i<cc;i++)
fout<<s[i]<<" ";
return 0;
}