Cod sursa(job #1691529)

Utilizator andreilucaLuca Andrei andreiluca Data 18 aprilie 2016 17:28:57
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 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("strmath.out");

string pattern, s;
vector<int> v;
vector<int> build_prefix(string);
void KMP();
int main()
{
	fin >> pattern;
	fin >> 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] ])
				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.size() && s[i] == pattern[k] )
		{
			k++; i++;
			ok = 1;
		}
		
		if (k == pattern.size())
		{
			q.push(i - k);
			k = v[k-1]-1;
			i--;
			i--;
		}
			
		else
		{
			if (ok)
			{
				k = v[k] - 1;
				i--;
				if (k < 0)
					k = 0;
			}	

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