Pagini recente » Cod sursa (job #2327053) | Cod sursa (job #2902475) | Cod sursa (job #1664276) | Cod sursa (job #2126555) | Cod sursa (job #2229877)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int N = 2000010;
char a[N],b[N];
int na,nb,cnt,p[N],sol[1010];
void prefix(),KMP();
int main()
{
f>>(a+1)>>(b+1);
prefix();
KMP();
g<<cnt<<'\n';
cnt=min(cnt,1000);
for(int i=1;i<=cnt;i++)
g<<sol[i]<<' ';
return 0;
}
void prefix()
{
na=strlen(a+1);
int q=0;
for(int i=2; i<=na; i++)
{
while(q&&a[i]!=a[q+1])q=p[q];
if(a[i]==a[q+1])q++;
p[i]=q;
}
}
void KMP()
{
nb=strlen(b+1);
int q=0;
for(int i=1; i<=nb; i++)
{
while(q&&b[i]!=a[q+1])q=p[q];
if(b[i]==a[q+1])q++;
if(q==na)
{
cnt++;
if(cnt<=1000)
sol[cnt]=i-na;
}
}
}