Cod sursa(job #1191049)

Utilizator BitOneSAlexandru BitOne Data 26 mai 2014 13:31:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <array>
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;
const int NMAX = 2000011;
const int MAXMATCHES = 1000;

size_t size;
vector<int> match;
array<int, NMAX> f;

void errorFunction(string p)
{
    f[0] = f[1] = 0;
    for(decltype(p.size()) i = 2; i <= p.size(); ++i)
    {
	int j;
	for(j = f[i - 1]; j && p[j] != p[i - 1]; j = f[j]);
	if(p[j] == p[i - 1]) ++j;
	f[i] = j;
    }
}

void KMP(string p, string s)
{
    int N, M, i, j;

    N = s.size();
    M = p.size();

    errorFunction(p);

    p.push_back(' ');
    s.push_back(' ');
    for(i = j = 0; i < N; )
    {
	if(s[i] == p[j])
	{
	    ++i, ++j;
	    if(M == j)
	    {
		++size;
		if(size < MAXMATCHES) match.push_back(i - M);
	    }
	}
	else if(j) j = f[j];
	else ++i;
    }
}

int main()
{
    string p, s;
    ifstream in{"strmatch.in"};
    ofstream out{"strmatch.out"};

    getline(in, p);
    getline(in, s);

    KMP(p, s);
    out << size << '\n';
    copy(match.begin(), match.end(), ostream_iterator<int>{out, " "});
    out << '\n';

    return EXIT_SUCCESS;
}