Cod sursa(job #1362749)

Utilizator radudorosRadu Doros radudoros Data 26 februarie 2015 15:11:55
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <string>
#include<vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int pi[2000001];
vector<int> sol;



void compute_prefix_function(string p)
{
	int m = p.length();
	pi[0] = -1;
	int k = -1;
	for (int q = 1; q < m; q++)
	{
		while (k > -1 && (p[k + 1] != p[q]))
			k = pi[k];
		if (p[k + 1] == p[q])
			k++;
		pi[q] = k;
	}
}

void kmp(string p,string s)
{
	compute_prefix_function(p);
	int n = s.length();
	int m = p.length();
	int q = -1;
	for (int i = 0; i < n; i++)
	{
		while (q>-1 && (p[q + 1] != s[i]))
			q = pi[q];
		if (p[q + 1] == s[i])
			q = q + 1;
		if (q == m - 1)
		{
			sol.push_back(i - m+1);
			q = pi[q];
		}
	}
}


int main()
{
	string p, s;
	fin >> p >> s;
	kmp(p, s);
	fout << sol.size()<<'\n';

	for (int i = 0; i<sol.size(); i++)
	{
		fout << sol[i] << ' ';
	}
}