Cod sursa(job #731517)

Utilizator test0Victor test0 Data 8 aprilie 2012 11:32:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <cstdio>
#include <vector>
#define MAX 2000002
using namespace std;
vector<int>v;
char a[MAX],b[MAX];
int u[MAX],n,nr;

void prefix(){
    int i,k;
    u[0]=k=-1;
    for(i=1;a[i]!='\n';n=i++){
        while(k>-1&&a[k+1]!=a[i])k=u[k];
        if(a[k+1]==a[i])k++;
        u[i]=k; }
}

void kmp(){
    int i,k;
    k=-1;
    for(i=0;b[i]!='\n';i++){
        while(k>-1&&a[k+1]!=b[i])k=u[k];
        if(a[k+1]==b[i])k++;
        if(k==n){
            nr++;
            if(nr<=1000)v.push_back(i-n);
            k=u[k]; }
    }
}

int main(){
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
        fgets(a,MAX,stdin);
        fgets(b,MAX,stdin);
    prefix();
    kmp();
      printf("%d\n",nr);
      for(int i=0;i<v.size();i++)printf("%d ",v[i]);
}