Pagini recente » Cod sursa (job #1661135) | Cod sursa (job #876167) | Cod sursa (job #630557) | Cod sursa (job #969122) | Cod sursa (job #2931968)
#include<fstream>
#include<cstring>
//#include<iostream>
using namespace std;
ifstream cin("input.in");
ofstream cout("output.out");
int urm[2000001];
char t[2000001],P[2000001];
int n,m;
void urmatorul(char *p)
{
int k=-1,x;
urm[0]=0;
for(x=1;x<m;x++)
{
while(k>0&&P[k+1]!=P[k])
k=urm[k];
if(p[k+1]==P[x]) k++;
urm[k]=k;
}
}
int poz[1002];
int main() {
int i,x=-1,p1=0;
int cnt=0;
cin.getline(P,2000000);
cin.getline(t,2000000);
n=strlen(t);
m=strlen(P);
urmatorul(P);
for(i=0;i<n;i++)
{
while(x>0&&P[x+1]!=t[i])x=urm[x];
if(P[x+1]==t[i])x++;
if(x==m-1)
{
p1++;
if(p1<=1000)
poz[p1]=i-m+1;
cnt++;
x=urm[x];
}
}
cout<<cnt<<'\n';
if(p1>1000)
p1=1000;
for(i=1;i<=p1;i++)
cout<<poz[i]<<' ';
}