Pagini recente » Cod sursa (job #2585606) | Cod sursa (job #1185565) | Cod sursa (job #2725304) | Cod sursa (job #2769104) | Cod sursa (job #1468417)
#include <iostream>
#include <string.h>
using namespace std;
int f[2000005],i,j,nmbMatches=0,matches[1005],k;
string pattern,text;
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
cin>>pattern>>text;
f[0]=-1;
for (i=1;i<pattern.size();++i)
{
k=f[i-1];
while (k!=-1 && pattern[k]!=pattern[i-1])
k=f[k];
f[i]=k+1;
}
i=0;
j=0;
while (i<text.size())
{
if (text[i]==pattern[j])
{
if (j==pattern.size()-1)
{
matches[nmbMatches]=i;
nmbMatches++;
j=f[j];
}
else
{
i++;
j++;
}
}
else
{
while (f[j]!=-1 && pattern[j]!=text[i])
{
j=f[j];
}
if (f[j]==-1) j=0,i++;
}
}
cout<<nmbMatches<<"\n";
for (i=0;i<nmbMatches;i++)
{
cout<<matches[i]<<" ";
}
}