Pagini recente » Cod sursa (job #1382769) | Cod sursa (job #994262) | Cod sursa (job #2213919) | Cod sursa (job #2447912) | Cod sursa (job #2747640)
#include <bits/stdc++.h>
/// folosind KMP
using namespace std;
int ans[2000001];
int pi[2000001];
char a[2000005];
char b[2000005];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin>>(a+1)>>(b+1);
int n=strlen(a+1);
int m=strlen(b+1);
pi[1]=0;
int k=0;
for(int i=2;i<=n;i++)
{
while((k>0) and (a[k+1]!=a[i]))
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
k=0;
int q=0;
for(int i=1;i<=m;i++)
{
while((k>0) and a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
if(k==n)
{
k=pi[n];
ans[++q]=i-n;
}
}
cout<<q<<'\n';
int min_afis=min(q,1000);
for(int i=1;i<=min_afis;i++)
{
cout<<ans[i]<<" ";
}
}