Pagini recente » Cod sursa (job #1582494) | Cod sursa (job #3037709) | Cod sursa (job #2133251) | Cod sursa (job #135476) | Cod sursa (job #2550718)
#include <bits/stdc++.h>
#define N 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char t[N],p[N];
int a[N],urm[N];///pozitiile in a
int n,m,k;
void citire()
{
fin.getline(p,N);
fin.getline(t,N);
n=strlen(p);m=strlen(t);
fin.close();
}
void prefix()
{
int j=0;
for(int i=1;i<n;++i)
{
while(j>0&&p[i]!=p[j])
j=urm[j-1];
if(p[i]==p[j]) j++;
urm[i]=j;
}
}
void kmp()
{
int q=0;
for(int i=0;i<m;++i)///in text
{
while(q>0&&p[q]!=t[i])
q=urm[q-1];
if(p[q]==t[i])q++;
if(q==n)///tot paternul
a[k++]=i-n+1;
}
}
int main()
{
citire();
prefix();
kmp();
fout<<k<<'\n';
if(k>1000) k=1000;
for(int i=0;i<k;++i) fout<<a[i]<<' ';
fout.close();
return 0;
}