Cod sursa(job #1006995)

Utilizator lucianRRuscanu Lucian lucianR Data 7 octombrie 2013 23:07:56
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <iostream>
#include <string.h>
#include <fstream>
#define STR_MAX 2000002
#define WORD_MAX 2000002

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

char str[STR_MAX], word[WORD_MAX];
int L[WORD_MAX], k = 1, m, n, ap[1000], a;

void prefix()
{
    L[1] = 0;
    for(int i = 2; i <=m; i++)
    {
        k = L[i-1];
        while(k > 0 && word[i] != word[k+1])
            k = L[k];
        if(word[i] == word[k+1])
            k++;
        L[i] = k;
    }
}

void KMP()
{
    k = 0;
    for(int i = 1; i <= n; i++)
    {
        while(k && word[k+1] != str[i])
            k = L[k];
        if(word[k+1] == str[i])
            k++;
        if(k == strlen(word)-1)
        {
            k = L[k];
            if(a < 1000)
                ap[a++] = i-m;
        }
    }
}

int main()
{
    in.getline(word, WORD_MAX, '\n');
    in.getline(str, STR_MAX, '\n');
    //cout<<word;
    m = strlen(word);
    n = strlen(str);
    for(int i = strlen(word)+1; i >= 1; i--)
        word[i] = word[i-1];
    for(int i = strlen(str)+1; i >= 1; i--)
        str[i] = str[i-1];
    str[0] = ' ';
    word[0] = ' ';
    prefix();
    KMP();
    cout << a << '\n';
    for(int i = 0; i < min(a, 1000); i++)
        cout << ap[i] << " ";
    return 0;
}