Cod sursa(job #1405198)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 28 martie 2015 22:19:46
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <string>
#define NMAX 2000001
using namespace std;

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

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 backtrack(unsigned int& wPos, unsigned int& mPos)
//{
//	if (t[wPos] > -1)
//	{
//		mPos += wPos - t[wPos];
//		wPos = t[wPos];
//	}
//	else
//	{
//		wPos = 0;
//		mPos++;
//	}
//}

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()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	// word to find
	getline(cin, a);
	scanf("\n");
	// string in which to find a
	getline(cin, b);
	n = a.size();
	m = b.size();

	build_table();
	kmp_search();

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