Pagini recente » Atasamentele paginii Clasament bhggggggggg65423.-6 | Istoria paginii runda/rar25 | Atasamentele paginii runda_de_verificare | Cod sursa (job #340983) | Cod sursa (job #2803251)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,nr,m;
int rez[2000005],urmator[2000005],v[2000005];
string s,pat;
void init()
{
int i,j;
urmator[0]=-1;
for(i=1; i<n; i++)
{
j=urmator[i-1];
while(j>=0&&pat[i]!=pat[j])
j=urmator[j];
if(j==-1)
{
if(pat[i]==pat[0])urmator[i]=0;
else urmator[i]=-1;
}
else urmator[i]=j+1;
}
}
void kmp()
{
n=pat.size();
m=s.size();
init();
urmator[0]=0;
int i,j;
int x;
v[0]=(s[0]==pat[0]?0:-1);
for(i=1; i<m; i++)
{
x=v[i-1];
while(x!=-1&&s[i]!=pat[x+1])
x=urmator[x];
if(x==-1)
{
if(s[i]==pat[0]) v[i]=0;
else v[i]=-1;
}
else
v[i]=x+1;
if(v[i]==n-1)
rez[++nr]=i+1-n;
}
fout<<nr<<'\n';
for(i=1; i<=nr; i++)
{
fout<<rez[i]<<" ";
}
}
int main()
{
fin>>pat;
fin.get();
fin>>s;
kmp();
return 0;
}