Cod sursa(job #1453467)

Utilizator CollermanAndrei Amariei Collerman Data 23 iunie 2015 16:50:55
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<cstring>
using namespace std;
ofstream fout("strmatch.out");
ifstream fin("strmatch.in");
const long int MMAX = 2000002;

int t, p, nr;
int table[MMAX], sol[MMAX];
char text[MMAX], pattern[MMAX];

void citire()
{
    fin >> (pattern+1) >> (text+1);
    t = strlen(text+1);
    p = strlen(pattern+1);
}

void buildTable()
{
    int x = 0;

    for(int k=2; k<=p; k++) {
        while(x && pattern[x+1] != pattern[k])
            x = table[x];
        if(pattern[x+1] == pattern[k])
            x++;
        table[k] = x;
    }
}

void match()
{
    for(int i=1, k=0; i<=t; i++) {
        while(k && pattern[k+1] != text[i])
            k = table[k];
        if(pattern[k+1] == text[i])
            k++;
        if(k == p) {
            if(nr <= 1000)
                sol[++nr] = i-k;
            else nr++;
            k = table[k];
        }
    }
}

void afis()
{
    fout << nr << '\n';
    for(int i=1; i<=nr && i<=1000; i++)
        fout << sol[i] << ' ';
    fin.close();
    fout.close();
}

int main()
{
    citire();
    buildTable();
    match();
    afis();
    return 0;
}