Cod sursa(job #750669)

Utilizator test1Trying Here test1 Data 22 mai 2012 19:25:38
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define TEST 0

void open_file(){
    if(TEST)
    {
        freopen("test.in","r",stdin);
        freopen("test.out","w",stdout);
    } else
    {
        freopen("strmatch.in","r",stdin);
        freopen("strmatch.out","w",stdout);
    }
}

char a[2000002],b[2000002];
int u[2000002],n,nr;

vector<int>v;

void prefix(){
    int i,k=-1;
    u[0]=-1;
    for(int i=1;(n=i)<strlen(a);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=-1;
    for(i=0;i<strlen(b);i++)
    {
        while(k>-1 && a[k+1] != b[i])k=u[k];
        if(a[k+1] == b[i])k++;
        if(k == n - 1)
        {
            nr++;
            if(nr < 1000) v.push_back( i-k );
            k=u[k];
        }
    }
}


int main(){

    open_file();

    scanf("%s ",a);
    scanf("%s ",b);

    prefix();

    kmp();

    //for(int i=0;i<n;i++)printf("%d ",u[i]);

    printf("%d\n",nr);

    for(int i=0;i<v.size();i++)printf("%d ",v[i]);

    return 0;
}