Cod sursa(job #1399025)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 24 martie 2015 15:24:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;

ifstream is("strmatch.in");
ofstream os("strmatch.out");

string P, T;
int n, m;
int cnt;
vector<int> S;
int ps[2000002];

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

int main()
{
	Read();
	Prefix();
	KMP();
	os << cnt << '\n';
	for ( const int& s : S )
		os << s << ' ';
	is.close();
	os.close();
	return 0;
}

void Read()
{
	string s;
	getline(is, s);
	P = " ";
	P += s;
	getline(is, s);
	T = " ";
	T += s;
	m = P.length() - 1;
	n = T.length() - 1;
}

void Prefix()
{
	int k = 0;
	ps[1] = 0;
	for ( int i = 2; i <= m; ++i )
	{
		while ( k > 0 && P[k + 1] != P[i] )
			k = ps[k];
			
		if ( P[k + 1] == P[i] )
			++k;
			
		ps[i] = k;
	}
}

void KMP()
{
	int k = 0;
	for ( int i = 1; i <= n; ++i )
	{
		while ( k > 0 && P[k + 1] != T[i] )
			k = ps[k];
			
		if ( P[k + 1] == T[i] )
			++k;
			
		if ( k == m )
		{
			++cnt;
			if ( S.size() < 1001 )
				S.push_back(i - m);
		}
	}
}