Pagini recente » Cod sursa (job #1255814) | Cod sursa (job #741490) | Cod sursa (job #409751) | Cod sursa (job #2024130) | Cod sursa (job #3141551)
/**
* avem un text cu lungimea m<=100 000 si un cuv de lungime n<=100 000
* cuv poate fi oricat de lungime
* det toate aparitiile cuv in text ca secv
**/
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000001],b[2000001];
int sol[1001],p[2000001],n,m,L,k;
int main()
{
fin>>a+1>>b+1;
n=strlen(a+1);
m=strlen(b+1);
//KMP=knuth-moris-pratt --> obtine timp de calcul liniar : n+m
//pas 1: facem o preprocesare pe cuv a si dupa vom construi pt fiecare poz i din a o val p[i]
// p[i] = lungimea maxima a unui sufix terminat la poz i care e totodata si prefix
L=0;
for(int i=2;i<=n;i++)
{
while(L!=0 && a[i]!=a[L+1])
{
L=p[L];
}
if(a[i]==a[L+1])
{
L++;
}
p[i]=L;
}
L=0;
for(int i=1;i<=m;i++)
{
while(L!=0 && b[i]!=a[L+1])
{
L=p[L];
}
if(b[i]==a[L+1])
{
L++;
}
if(L==n)
{
k++;
if(k<=1000)
{
sol[k]=i-n+1;//cu indexare de la 1
}
L=p[L];
}
}
fout<<k<<"\n";
if(k>1000)
{
k=1000;
}
for(int i=1;i<=k;i++)
{
fout<<sol[i]-1<<" ";
}
return 0;
}