Pagini recente » Cod sursa (job #1228407) | Cod sursa (job #3033125) | Cod sursa (job #605394) | Cod sursa (job #987917) | Cod sursa (job #1468420)
#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+j<text.size())
{
if (text[i+j]==pattern[j])
{
if (j==pattern.size()-1)
{
matches[nmbMatches]=i;
nmbMatches++;
j=f[j];
}
else
{
j++;
}
}
else
{
while (f[j]!=-1 && pattern[j]!=text[i+j])
{
j=f[j];
}
if (f[j]==-1) j=0,i++;
}
}
cout<<nmbMatches<<"\n";
for (i=0;i<nmbMatches;i++)
{
cout<<matches[i]<<" ";
}
}