Cod sursa(job #1188158)

Utilizator xtreme77Patrick Sava xtreme77 Data 18 mai 2014 23:36:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <cstdio>
#include <cstring>
const int MAX = 2000010;
using namespace std;
int next[MAX],n,m,sol=0,v[MAX];
char a[MAX],b[MAX];
void prec();
int main ( ){
    int k=0;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(a+1);n=strlen(a+1);
    gets(b+1);m=strlen(b+1);
    prec();
    for(int i=1;i<=m;++i){
        while(k>0 and b[i]!=a[k+1])k=next[k];
        if(not (b[i]!=a[k+1]))++k;
        if(k==n){
            if(sol<1000)
                v[++sol]=i-n;
            else ++sol;
        }
    }
    for(printf("%d\n",sol),k=1;k<=sol;(k<=1000)?printf("%d ",v[k]):0,++k);
}
void prec(){
    int k=0;
    for(int i=2;i<=n;++i){
        while(k>0 and a[k+1]!=a[i])k=next[k];
        if(a[k+1]==a[i])++k;
        next[i]=k;
    }
}