Cod sursa(job #1198243)

Utilizator mihai995mihai995 mihai995 Data 15 iunie 2014 04:46:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

const int N = 2 + 2e6, AnsSize = 1e3;

char text[N], pattern[N];
int Z[N], match[N], ans[N];

void runSequence(char text[], char pattern[], int Z[], int match[]){
    int best = 0;
    for (int i = 1 + (text == pattern); text[i] ; i++){
        if ( i < best + match[best] )
            match[i] = min( best + match[best] - i, Z[i - best + 1] );
        while ( text[ i + match[i] ] && pattern[ match[i] + 1 ] == text[ i + match[i] ] )
            match[i]++;
        if (best + match[best] < i + match[i])
            best = i;
        //cout << i << ": " << match[i] << '\n';
    }
}

void strmatch(char text[], char pattern[], int match[]){
    runSequence(pattern, pattern, Z, Z);
    runSequence(text, pattern, Z, match);
}

int main(){
    ifstream in("strmatch.in");
    in >> (pattern + 1) >> (text + 1);
    in.close();

    strmatch(text, pattern, match);

    int n = strlen(pattern + 1);
    for (int i = 1 ; text[i] ; i++)
        if ( match[i] == n )
            ans[ ++ans[0] ] = i;

    ofstream out("strmatch.out");

    out << ans[0] << '\n';
    for (int i = 1 ; i <= ans[0] && i <= AnsSize ; i++)
        out << ans[i] - 1 << ' ';
    out << '\n';

    out.close();

    return 0;
}