Cod sursa(job #1691856)

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

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

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

	build_prefix(pattern);
	KMP();/*
	fout << '\n';
	for (int i = 0; i < pattern.size(); i++)
		fout << v[i];
	fout << '\n' << pattern;
	*/
	
	return 0;
}
void build_prefix(string p)
{
	v[0] = -1;
	v[1] = 0;
	int k=0;
	for (int i = 2; i < p.size(); i++)
	{
		k = v[i - 1];
		while (k!=-1&&p[i-1] != p[k])
			k = v[k];
		v[i] = k + 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!=-1&&pattern[k + 1] != s[i])
			k = v[k];
		k++;
		if (k == pattern.size()-1)
		{
			k = v[k];
			
			//if (q.size() < 1000)
				q.push(i-pattern.size()+1);
		}
		
	}
_end:
	int contor = 0;
	fout << q.size()<<'\n';
	while (!q.empty() && contor <= 1000)
	{
		contor++;
		fout << q.front() << ' ';
		q.pop();
	}
	
}