Cod sursa(job #2032727)

Utilizator robuvedVictor Robu robuved Data 5 octombrie 2017 17:11:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

vector<int> ComputeLPS(string P)
{
	vector<int> lps(P.size(), 0);
	lps[0] = -1;
	int k = -1;
	for (int i = 1; i < lps.size(); i++)
	{
		while (k >= 0 && P[k + 1] != P[i])
		{
			k = lps[k];
		}
		if (P[k + 1] == P[i])
			k++;
		lps[i] = k;
	}
	return lps;
}
vector<int> KMP(string T, string P)
{
	vector<int> lps = ComputeLPS(P);
	vector<int> occurrences;
	int k = -1;
	for (int i = 0; i < T.size(); i++)
	{
		while (k >= 0 && P[k + 1] != T[i])
		{
			k = lps[k];
		}
		if (P[k + 1] == T[i])
			k++;
		if (k == P.size() - 1)
		{
			occurrences.push_back( i - P.size() + 1);
			k = lps[k];
		}
	}
	return occurrences;
}
int main()
{
	string A, B;
	in >> A >> B;
	vector<int> occ = KMP(B, A);
	out << occ.size() << endl;
	for (int i = 0; i< occ.size()  && i < 1000; i++)
	{
		out << occ[i] << ' ';
	}
}