Pagini recente » Cod sursa (job #1775971) | Cod sursa (job #2647185) | Cod sursa (job #2218054) | Cod sursa (job #1454385) | Cod sursa (job #3141554)
/**
* 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];
char A[2000001],B[2000001];
int sol[1001],p[2000001],n,m,L,k;
int main()
{
fin>>A>>B;
strcpy(a+1,A);
strcpy(b+1,B);
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;
}