Cod sursa(job #1691563)

Utilizator andreilucaLuca Andrei andreiluca Data 18 aprilie 2016 19:17:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

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

string pattern, s, space(" ");
vector<int> v;
vector<int> build_prefix(string);
void KMP();
int main()
{
	fin >> pattern;
	fin >> s;
	pattern =space+pattern;
	//s = space + s;

	v=build_prefix(pattern);
	KMP();
	/*
	for (int i = 0; i < v.size(); i++)
		fout << v[i];
	fout << '\n' << pattern;
	*/
	
	return 0;
}
vector<int> build_prefix(string p)
{
	vector<int> v;
	v.reserve(p.size());
	v.push_back(0);
	if (p[0] == p[1])
		v.push_back(1);
	else
		v.push_back(0);
	for (int i = 2; i < p.size(); i++)
	{
		if (p[i] != p[0])
		{
			if (p[i] != p[v[i-1]+1])
				v.push_back(0);
			else
				v.push_back(v[i - 1] + 1);

		}
		else
			v.push_back(1);
	}
	return v;
}
void KMP()
{
	int k=0;
	bool ok;
	queue<int> q;
	for (int i = 0; i < s.size(); i++)
	{
		
		ok = 0;
		while (k&&pattern[k + 1] != s[i])
			k = v[k];
		if (pattern[k + 1] == s[i])
			k++;
		if (k == pattern.size()-1)
		{
			k = v[k];
			//if (q.size() < 1000)
				q.push(i-pattern.size()+2);
		}
		
	}
_end:
	int contor = 0;
	fout << q.size()<<'\n';
	while (!q.empty() && contor <= 1000)
	{
		contor++;
		fout << q.front() << ' ';
		q.pop();
	}
	
}