Cod sursa(job #940909)

Utilizator andreiagAndrei Galusca andreiag Data 17 aprilie 2013 14:16:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
// Potrivirea sirurilor KMP

#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <fstream>

#define SIZE 2000001

using namespace std;

string A, B;

int T[SIZE];

void process_word(string &A) {
    int s = A.size();
    T[0] = -1;
    T[1] =  0;
    int pos = 2, cnd = 0;
    while(pos < s) {
        if (A[cnd] == A[pos - 1]) {cnd++; T[pos] = cnd; pos++;}
        else if(cnd > 0) {cnd = T[cnd];}
        else {T[pos] = 0; pos++;}
    }
    /*
    for(int i = 0; i < s; i++) cout << T[i] << ' ';
    cout << endl; */
}

int main()
{
    //freopen("strmatch.in", "r", stdin);
    //freopen("strmatch.out", "w", stdout);

    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");

    getline(fin, A);
    getline(fin, B);
    //cout << A << endl << B << endl;

    process_word(A);

    vector<int> found;

    int sa = A.size();
    int sb = B.size();
    int count = 0;
    int m = 0, i = 0;
    while(m + sa <= sb && count < 1000) {
        while(i < sa && A[i] == B[m + i]) i++;
        if (i == sa) {found.push_back(m);
                      //cout << m << endl;
                      count++;
                      m = m + i - 1 - T[sa - 1];
                      i = T[sa - 1]; }

        else {m = m + i - T[i]; if(i) i = T[i];}
    }

    fout << count << endl;
    if (count) fout << found[0];
    for(int j = 1; j < found.size(); j++)
        fout << ' ' << found[j];
    fout << endl;

    return 0;
}