Cod sursa(job #1090780)

Utilizator SeekHunt1334Septimiu Bodica SeekHunt1334 Data 23 ianuarie 2014 08:08:27
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

int n, m, k;
string P, T;
vector<int> pi;
vector<int> sols;

void Read();
void Prefix();
void KMP();
void Write();

int main()
{
	Read();
	Prefix();
	KMP();
	Write(); fout << '\n';

	fin.close();
	fout.close();
	return 0;
}

void Write()
{
    fout << sols.size() << '\n';

    vector<int>::iterator it;
    for (it = sols.begin(); it != sols.end(); ++it)
        fout << *it << ' ';
}

void KMP()
{
	int q = 0;
	for (int i = 1; i <= n; ++i)
	{
		while ( q > 0 && P[q] != T[i-1] )
			q = pi[q];
		if ( P[q] == T[i-1] )
			q++;
		if ( q == m )
		{
            sols.push_back(i-m);
			q = pi[q];
		}
	}
}

void Prefix()
{
	m = P.length();
	n = T.length();

	pi.resize(n+1);

	for (int q = 2; q <= m; ++q)
	{
		while ( k > 0 && P[k] != P[q-1] )
			k = pi[k];
		if ( P[k] == P[q-1] )
			k++;
		pi[q] = k;
	}
}

void Read()
{
	fin >> P >> T;
}