Pagini recente » Cod sursa (job #1366412) | Cod sursa (job #500522) | Cod sursa (job #1101579) | Cod sursa (job #3226212) | Cod sursa (job #467488)
Cod sursa(job #467488)
/* 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<string>
#include<fstream>
using namespace std;
fstream f("strmatch.in",ios::in),g("strmatch.out",ios::out);
char p[2000012],t[2000012];
long pi[2000012],m,n,nrap,aparitii[1001];
void citire()
{
f.get( p+1, 2000010 ); f.get();
f.get( t+1, 2000010 );
n = strlen( t+1 );
m = strlen( p+1 );
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)
{
k=pi[k];
++nrap;
if(nrap<=1000)
aparitii[nrap]=i-m;
}
}
}
void afisare()
{
g<<nrap<<"\n";
for(int i=1;i<=nrap;i++)
g<<aparitii[i]<<" ";
}
int main()
{
citire();
calc_prefix();
kmp();
afisare();
g.close();
return 0;
}