Pagini recente » Cod sursa (job #279187) | Cod sursa (job #213986) | Cod sursa (job #3197035) | Cod sursa (job #1041681) | Cod sursa (job #2175101)
#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],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=str1.length(); n=str2.length();
create_lps();
KMP();
fout<<lenrez<<'\n';
for (int i=1;i<=lenrez;++i) fout<<rez[i]<<" ";
return 0;
}