Pagini recente » Cod sursa (job #417173) | Cod sursa (job #1815687) | Cod sursa (job #148394) | Cod sursa (job #2444881) | Cod sursa (job #505656)
Cod sursa(job #505656)
#include <stdio.h>
#include <string.h>
#define Max 2000002
#include <algorithm>
using namespace std;
char T[Max], P[Max];
int n, m, L[Max], a[1002];
void prefix(){
int i,k;
L[1]=0;
for (i=2; i<=n; i++){
k=L[i-1];
while (k>0 && P[i]!=P[k+1]) k=L[k];
if (P[i]==P[k+1]) k++;
L[i]=k;
}
}
void match()
{
int k, nr, i;
k=0; nr=0;
for (i=1; i<=m; i++){
while (k>0 && T[i]!=P[k+1]) k=L[k];
if (T[i]==P[k+1])
k++;
if (k==n)
{
nr++;
if (nr<=1000)
a[nr]=i-n;
k=L[n];
}
}
printf("%d\n", nr);
for (i=1;i<=min(1000,nr); i++) printf("%d ",a[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(P+1, Max, stdin); fgets(T+1, Max, stdin);
n=strlen(P+1)-1; m=strlen(T+1)-1;
prefix();
match();
return 0;
}