Cod sursa(job #903895)

Utilizator tanduraDomnita Dan tandura Data 3 martie 2013 12:32:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

int pi[2000001];
char a[2000001];
char b[2000001];
vector<int> in;

void prefix(char b[])
{
    int m=strlen(b);
    int k=-1;
    pi[0]=-1;
    for(int q=1;q<m;++q)
    {
        while(k>-1 &&b[k+1]!=b[q])
            k=pi[k];
        if(b[k+1]==b[q])
            ++k;
        pi[q]=k;
    }
}
void kmp(char a[], char b[])
{
    int n=strlen(a);
    int m=strlen(b);
    prefix(b);
    int q=-1;
    for(int i=0;i<n;++i)
    {
        while(q>-1&&b[q+1]!=a[i])
            q=pi[q];
        if(a[i]==b[q+1])
            ++q;
        if(q==m-1){
            in.push_back(i-m+1);
            q=pi[q];}
    }
}
void citire()
{
    freopen("strmatch.in","r",stdin);
    scanf("%s",&b);
    scanf("%s",&a);
}
int main()
{
    citire();
    kmp(a,b);
    freopen("strmatch.out","w",stdout);
    int po=in.size();
    printf("%d\n",po);
    for(int i=0;i<min(1000,po);++i)
        printf("%d ",in[i]);
    return 0;
}