Cod sursa(job #1691552)

Utilizator andreilucaLuca Andrei andreiluca Data 18 aprilie 2016 18:38:13
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 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=1;
	bool ok;
	queue<int> q;
	for (int i = 1; i < s.size(); i++)
	{
		
		ok = 0;
		while (k<pattern.size() && s[i] == pattern[k] )
		{
			k++; i++;
			ok = 1;
		}
		
		if (k == pattern.size()&&q.size()<=1000)
		{
			q.push(i - k);
			k = v[k-1];
			i--;
			i--;
		}
			
		else
		{
			if (ok)
			{
				k = v[k];
				i--;
				i--;
				if (k < 0)
					k = 1;
			}	

			else
				k = 1;
		}
	}
	_end:
	fout << q.size()<<'\n';
	while (!q.empty())
	{
		fout << q.front() << ' ';
		q.pop();
	}
	
}