Mai intai trebuie sa te autentifici.

Cod sursa(job #1426439)

Utilizator ButnaruButnaru George Butnaru Data 29 aprilie 2015 18:44:24
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <stdio.h>
#include <string.h>
#include <values.h>
#define lengmax 2000000
using namespace std;
char s[lengmax],ss[lengmax];
long i,n,m,k,urm[lengmax],nr=0,sol[1001];
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s+1); n=strlen(s+1);
gets(ss+1); m=strlen(ss+1);
urm[1]=0; k=0;
for (i=2;i<=n;i++){
while (k>0 && s[i]!=s[k+1]) k=urm[k];
if (s[i]==s[k+1]) k++;
urm[i]=k;
}
for (i=1,k=0;i<=m;i++){
while (k>0 && ss[i]!=s[k+1]) k=urm[k];
if (ss[i]==s[k+1]) k++;
if (k==n) {
nr=nr+1;
if (nr<=1000) sol[nr]=i-n;
k=urm[k];}
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=1;i<=nr;i++) printf("%d ",sol[i]);
return 0;
}