Pagini recente » Cod sursa (job #765911) | Cod sursa (job #3325399) | Cod sursa (job #86672) | Cod sursa (job #443013) | Cod sursa (job #3341990)
#include <fstream>
#include <cstring>
#define LGMAX 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char s1[LGMAX], s2[LGMAX];
int lg1, lg2, k, nr, pi[LGMAX], st[1005];
int main()
{
fin>>s1>>s2;
lg1=strlen(s1);
lg2=strlen(s2);
for(int i=1; i<lg1; i++)
{
while (k && s1[k]!=s1[i])
k=pi[k-1];
if(s1[k]==s1[i])
k++;
pi[i]=k;
}
k=0;
for(int i=0; i<lg2; i++)
{
while (k && s1[k]!=s2[i])
k=pi[k-1];
if(s1[k]==s2[i])
{
k++;
if(k==lg1)
{
nr++;
if(nr<=1000)
st[nr]=i-k+1;
k=pi[k-1];
}
}
}
fout<<nr<<'\n';
for(int i=1; i<=nr && i<=1000; i++)
fout<<st[i]<<' ';
return 0;
}