Pagini recente » Cod sursa (job #3318364) | Cod sursa (job #3316893) | Cod sursa (job #3316871) | Cod sursa (job #159756) | Cod sursa (job #3342013)
#include <iostream>
#include <fstream>
#include <cstring>
#define NMax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char sir[NMax],s[NMax];
int t[NMax],sol=0,rez[1005];
void prefix(char s[])
{
int j=0;
t[0]=0;
for(int i=1; s[i]; i++)
{
while(s[i]!=s[j] && j!=0)
j=t[j-1];
if(s[i]==s[j])
j++;
t[i]=j;
}
}
int main()
{
fin>>s>>sir;
prefix(s);
int j=0;
for(int i=0; sir[i]; i++)
{
while(sir[i]!=s[j] && j!=0)
j=t[j-1];
if(sir[i]==s[j])
j++;
if(j==strlen(s))
{
sol++;
if(sol<=1000)
rez[sol]=i-j+1;
j=t[j-1];
}
}
fout<<sol<<"\n";
for(int i=1; i<=min(sol,1000); i++)
{
fout<<rez[i]<<" ";
}
return 0;
}