Cod sursa(job #1006966)

Utilizator lucianRRuscanu Lucian lucianR Data 7 octombrie 2013 22:24:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <string.h>
#include <fstream>
#define STR_MAX 2000000
#define WORD_MAX 2000000

using namespace std;
ifstream in("8.in");
ofstream out("8.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];
            ap[a++]=i-m;
        }
    }
}

int main()
{
    in.getline(word, WORD_MAX, '\n');
    in.getline(str, STR_MAX, '\n');
    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();
    out<<a<<endl;
    for(int i=0; i<a; i++)
        out<<ap[i]<<" ";
    return 0;
}