Mai intai trebuie sa te autentifici.
Cod sursa(job #505699)
Utilizator | Data | 3 decembrie 2010 17:39:53 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.87 kb |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
char T[2000002],P[2000002];
int n,L[2000002],m,sol[1002],j;
void prefix()
{
int i,k;
L[1]=0;
for (i=2; i<=n; i++)
{
k=L[i-1];
while (k>0 && P[k+1]!=P[i])
k=L[k];
if (P[k+1]==P[i])
k++;
L[i]=k;
}
}
void rezolva()
{
int i,k;
k=0;
for(i=1;i<=m;i++)
{
while(k>0 && P[k+1]!=T[i])
k=L[k];
if (P[k+1]==T[i])
k++;
if (k==n)
{
sol[0]++;
if(sol[0]<=1000) sol[sol[0]]=i-n;
k=L[k];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(P+1,2000002,stdin);
fgets(T+1,2000002,stdin);
n=strlen(P+1)-1;
m=strlen(T+1)-1;
prefix();
rezolva();
printf("%d\n",sol[0]);
for(j=1;j<=min(sol[0],1000);j++)
printf("%d ",sol[j]);
return 0;
}