Cod sursa(job #955054)

Utilizator cousin.batmanVaru Batman cousin.batman Data 30 mai 2013 20:20:58
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <string>
#include <fstream>
#include <list>
#include <iostream>
 
using namespace std;
 
void create_automaton(const string &pattern, int *pi){
    int i, k=0;
}
 
list<int> find_matches(const string &pattern, const string &text, int *pi){
    list<int> result;
    int i, k=0;
 
    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()], i, k;
 
    create_automaton(pattern,  pi);
    //CREATE AUTOMATON
    pi[0] = 0;
    k = 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;
    }
    k=0;
    //FIND MATCHES
    list<int> result;
    for(i=0; i<text.size(); i++){
        while(k>0 && text[i]!=pattern[k])
            k=pi[k-1];
 
        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;
    }
 
    out<<result.size()<<endl;
    for(int i: result)
        out<<i<<" ";
 
    in.close();
    out.close();
    return 0;
}