Pagini recente » Cod sursa (job #893370) | Cod sursa (job #1435100) | Cod sursa (job #2488204) | Cod sursa (job #1650695) | Cod sursa (job #2717189)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[2000005],s2[2000005];
int prefix[2000005],n,m;
vector<int>ans;
int main()
{
fin>>s1;
fin>>s2;
n=strlen(s1);
m=strlen(s2);
int j=0;
for(int i=1;i<=n-1;i++)
{
while(j>0&&s1[i]!=s1[j])
j=prefix[j-1];
if(s1[i]==s1[j])
j++;
prefix[i]=j;
}
j=0;
for(int i=1;i<m;i++)
{
while(s2[i]!=s1[j]&&j>0)
j=prefix[j-1];
if(s2[i]==s1[j])
j++;
if(j==n)
ans.push_back(i-n+1);
}
fout<<ans.size()<<'\n';
int val=ans.size();
val=min(val,1000);
for(int i=0;i<val;i++)
fout<<ans[i]<<" ";
return 0;
}