Pagini recente » Cod sursa (job #3278652) | Cod sursa (job #36850) | Cod sursa (job #799623) | Cod sursa (job #2770308) | Cod sursa (job #467478)
Cod sursa(job #467478)
/* p[] - pattern, t[] - text
numerotam de la 1. k reprezinta lungimea prefixului-sufix maxim la pasul curent
si e salvat in vectorul pi[]. Exemplu:
ababbababaac
001201234310 */
#include<fstream>
using namespace std;
char p[2000002],t[2000002];
long pi[2000002],m,n,nrap,aparitii[1001];
void citire()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",p+1,t+1);
m=strlen(p+1);
n=strlen(t+1);
//p[0]=t[0]='g';
//printf("%s\n%s",p,t);
nrap=0;
}
void calc_prefix()
{
int k=0;
pi[1]=0;
for(int i=2;i<=m;i++)
{
while((k>0)&&(p[k+1]!=p[i]))
k=pi[k];
if(p[k+1]==p[i])
k++;
pi[i]=k;
}
}
void kmp()
{
int k=0;
for(int i=1;i<=n;i++)
{
while((k>0)&&(p[k+1]!=t[i]))
k=pi[k];
if(p[k+1]==t[i])
k++;
if(k==m)
{
nrap++;
if(nrap<1000)
aparitii[nrap]=i-m;
}
}
}
void afisare()
{
printf("%ld\n",nrap);
for(int i=1;i<=nrap;i++)
printf("%ld ",aparitii[i]);
}
int main()
{
citire();
calc_prefix();
kmp();
afisare();
return 0;
}