Pagini recente » Cod sursa (job #622613) | Cod sursa (job #2951652) | Cod sursa (job #2797860) | Cod sursa (job #2180286) | Cod sursa (job #2175121)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char str1[2000001],str2[2000001];
int k=1,len,n,m,lps[2000001],i,j,rez[2000001],lenrez;
void create_lps()
{
lps[0]=0;
while (k<m)
{
if (str1[k]==str1[len])
{
len++;
lps[k]=len;
k++;
}
else
{
if (len>0) len=lps[len-1];
else lps[k]=0,k++;
}
}
}
void KMP()
{
k=1;
while (i<n)
{
if (str2[i]==str1[j]) i++,j++;
if (j==m)
{
lenrez++;
rez[k++]=i-j;
j=lps[j-1];
}
else
{
if(i<n&&str1[j]!=str2[i])
{
if (j!=0)
{
j=lps[j-1];
}
else i++;
}
}
}
}
int main()
{
fin>>str1>>str2;
m=strlen(str1); n=strlen(str2);
create_lps();
KMP();
if (lenrez>1000) fout<<1000<<'\n';
else fout<<lenrez<<'\n';
for (int i=1;i<=(lenrez>1000?1000:lenrez);++i) fout<<rez[i]<<" ";
return 0;
}