Pagini recente » Cod sursa (job #1426742) | Cod sursa (job #1659715) | Clasament runda_3_star | Cod sursa (job #2619760) | Cod sursa (job #2175361)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str1,str2;
int k=1,len,n,m,lps[2000001],i,j,rez[2000001];
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)
{
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=str1.length(); n=str2.length();
create_lps();
KMP();
k--;
fout<<k<<'\n';
for (int z=1;z<=(k>1000?1000:k);++z) fout<<rez[z]<<" ";
return 0;
}