Cod sursa(job #670581)

Utilizator laurionLaurentiu Ion laurion Data 29 ianuarie 2012 14:47:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<fstream>
#include<iostream>
#include<vector>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

vector<int> matches;
string sir, subsir;
int pi[2000000+10];

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

    getline(fin, subsir);
    getline(fin, sir   );
//    subsir.insert(subsir.begin(),'-');//incepem de la 1, nu de la 0 //TODO
//    sir.insert(sir.begin(),'-');      //incepem de la 1, nu de la 0 //TODO

    if (sir.size()<subsir.size()) {
        fout<<0<<'\n';
        return 0;
    }

    int k=0;
    pi[1]=0;
    for(int i=1; i<subsir.length(); ++i) {
        while(k>0 && subsir[i] != subsir[k])
            k=pi[k];
        if(subsir[i] == subsir[k])
            k++;
        pi[i+1]=k;
    }

    k=0;
    int nr=0;
    for(int i=0; i<sir.length(); ++i) {
        while(k>0   &&  sir[i] != subsir[k])
            k=pi[k];
        if(sir[i]   ==  subsir[k])
            k++;
        if(k==subsir.length()) { //match
            if(matches.size()<1000) {
                matches.push_back(i-subsir.length()+1);
            }
            nr++;
        }
    }

    fout<<nr<<'\n';
    for(int i=0; i<matches.size(); ++i) {
        fout<<matches[i]<<' ';
    }
    fout<<'\n';
    fout.close();
    return 0;
}