Cod sursa(job #735558)

Utilizator BitOneSAlexandru BitOne Data 16 aprilie 2012 19:25:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011

using namespace std;

string s, p;
vector< int > match;
int failureFunction[N_MAX];

int main()
{
    int N, M, i, j, count=0;
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    getline(in, p);
    getline(in, s);
    N=s.size(); M=p.size();
    s.push_back(' '); p.push_back(' ');
    for(i=2, j=0; i <= M; ++i)
    {
        for(; p[i-1] != p[j] && j; j=failureFunction[j]);
        if(p[i-1] == p[j])
            ++j;
        failureFunction[i]=j;
    }
    for(i=j=0; i < N; )
    {
        if(p[j] == s[i])
        {
            ++i, ++j;
            if(M == j)
            {
                ++count;
                if(count <= 1000)
                    match.push_back(i-M);
            }
        }
        else if(j)
                j=failureFunction[j];
             else ++i;
    }
    out<<count<<'\n';
    copy(match.begin(), match.end(), ostream_iterator<int>(out, " "));
    out<<'\n';
    return EXIT_SUCCESS;
}