Nu aveti permisiuni pentru a descarca fisierul grader_test10.ok
Cod sursa(job #552368)
Utilizator | Data | 12 martie 2011 10:21:04 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.01 kb |
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char p[2000005], t[2000005];
int n, m, b[2000005], a[2000005];
void citire()
{
fgets(p,2000005);
fgets(t,2000005);
m=strlen(p);
n=strlen(t);
}
void kmpPreprocess()
{
int i=0, j=-1;
b[i]=j;
while (i<m)
{
while (j>=0 && p[i]!=p[j])
j=b[j];
i++;
j++;
b[i]=j;
}
}
void kmpSearch()
{
int i=0, j=0;
while (i<n)
{
while (j>=0 && t[i]!=p[j])
j=b[j];
i++;
j++;
if (j==m)
{
a[++a[0]]=i-j;
j=b[j];0
}
}
}
void afisare()
{
printf ("%d\n",a[0]);
for (int i=1; i<=min(1000,a[0]); i++)
printf ("%d ",a[i]);
printf ("\n");
}
int main()
{
freopen ("strmatch.in","r",stdin);
//freopen ("strmatch.out","w",stdout);
citire();
kmpPreprocess();
kmpSearch();
afisare();
return 0;
}