Cod sursa(job #1203777)

Utilizator tudormaximTudor Maxim tudormaxim Data 1 iulie 2014 11:59:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string P,T;
int URM[2000005];
vector<int> result;
int nrSol;
void prefix()
{
    URM[1] = 0;
    int k = 0;
    for(int q=2; q<P.size(); q++)
    {
        while(k > 0 && P[k + 1] != P[q])
            k = URM[k];
        if(P[k + 1] == P[q])
            k = k + 1;
        URM[q] = k;
    }
}
void match()
{
    int q = 0;
    int m = P.size() - 1;
    nrSol = 0;
    for(int i=0;i<T.size();i++)
    {
        while(q > 0 && P[q + 1] != T[i])
            q = URM[q];
        if(P[q + 1] == T[i])
            q = q + 1;
        if(q == m)
        {
            ++nrSol;
            if(nrSol<=1000)
                result.push_back(i - m + 1);
        }
    }
}
int main()
{
    in>>P>>T;
    P = '#' + P;
    prefix();
    match();
    out<<nrSol<<'\n';
    for(int i=0;i<result.size();i++)
        out<<result[i]<<' ';
    return 0;
}