Pagini recente » Cod sursa (job #2553399) | Cod sursa (job #1457197) | Cod sursa (job #2677019) | Cod sursa (job #688940) | Cod sursa (job #2876147)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002],b[2000002];
int sol[2000002],lps[2000002],k;
int main()
{int n,m,x;
f.getline(a,2000002);
f.getline(b,2000002);
n=strlen(a+1);
m=strlen(b+1);
for (int i=2;i<=n;i++) {x=lps[i-1];
while (x>0 && a[x+1]!=a[i]) x=lps[x];
if (a[x+1]==a[i]) x++;
lps[i]=x;
}
x=0;
for (int i=1;i<=m;i++) {while (x>0 && a[x+1]!=b[i]) x=lps[x];
if (a[x+1]==b[i]) x++;
if (x==n) k++,sol[k]=i-n;
}
g<<k<<'\n';
for (int i=1;i<=min(1000,k);i++) g<<sol[i]<<' ';
}