Cod sursa(job #955051)

Utilizator cousin.batmanVaru Batman cousin.batman Data 30 mai 2013 20:17:50
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <string>
#include <fstream>
#include <list>
#include <iostream>

using namespace std;

void create_automaton(const string &pattern, int *pi){
    int i, k=0;
    pi[0] = 0;

    for(i=1; i<pattern.size(); i++){
        while(k>0 && pattern[i]!=pattern[k])
            k=pi[k];

        if(pattern[i]==pattern[k])
            k++;
        pi[i] = k;
    }
}

list<int> find_matches(const string &pattern, const string &text, int *pi){
    list<int> result;
    int i, k=0;

    for(i=0; i<text.size(); i++){
        while(k>0 && text[i]!=pattern[k])
            k=pi[k];
        if(text[i] == pattern[k])
            k++;

        if(k==pattern.size()){
            result.push_back(i-pattern.size()+1);
            k=pi[k-1];
        }
        //if(result.size()==1000)
//            return result;
    }
    return result;
}

int main(){
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    string pattern , text;
    getline(in, pattern);
    getline(in, text);

    int pi[pattern.size()];

    create_automaton(pattern,  pi);
    list<int> result = find_matches(pattern, text, pi);

    out<<result.size()<<endl;
    for(int i: result)
        out<<i<<" ";

    in.close();
    out.close();
    return 0;
}