Cod sursa(job #1405210)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 28 martie 2015 22:34:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <string>
#define NMAX 2000001
using namespace std;

int t[NMAX];
unsigned int pos[1000], n, m, nr;
string a, b;

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

void build_table()
{
	unsigned int wPos = 2, cnd = 0;
	t[0] = -1;
	t[1] = 0;
	
	while (wPos < n)
	{
		if (a[wPos - 1] == a[cnd])
		{
			cnd++;
			t[wPos] = cnd;
			wPos++;
		}
		else
			if (cnd > 0)
			{
				cnd = t[cnd];
			}
			else
			{
				t[wPos] = 0;
				wPos++;
			}
	}
}

void kmp_search()
{
	unsigned int matchPos = 0, wordPos = 0;

	while (matchPos + wordPos < m)
	{
		bool backtrack = true;
		if (a[wordPos] == b[matchPos + wordPos])
		{
			backtrack = false;
			// found a match of word in b
			if (wordPos == n - 1)
			{
				nr++;
				if (nr <= 1000)
				{
					// save start position
					pos[nr - 1] = matchPos;
				}
				backtrack = true;
			}
			else
			{
				wordPos++;
			}
		}
		
		if (backtrack)
		{
			if (t[wordPos] > -1)
			{
				matchPos += wordPos - t[wordPos];
				wordPos = t[wordPos];
			}
			else
			{
				wordPos = 0;
				matchPos++;
			}
		}
	}
}

int main()
{
	// word to find
	getline(f, a);
	// string in which to find a
	getline(f, b);
	n = a.size();
	m = b.size();

	if (m == n)
	{
		if (a == b)
		{
			g << 1 << "\n" << 0;
		}
		else
		{
			g << 0;
		}
		return 0;
	}

	build_table();
	kmp_search();

	g << nr << "\n";
	for (int i = 0; i < (nr < 1000 ? nr : 1000); i++)
	{
		g << pos[i] << " ";
	}
	return 0;
}