Cod sursa(job #1405137)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 28 martie 2015 21:36:05
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.63 kb
#include <iostream>
#include <string>
using namespace std;

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

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)
	{
		if (a[wordPos] == b[matchPos + wordPos])
		{
			// found a match of word in b
			if (wordPos == n - 1)
			{
				nr++;
				if (nr <= 1000)
				{
					// save start position
					pos[nr - 1] = matchPos;
				}
				backtrack(wordPos, matchPos);
			}
			else
			{
				wordPos++;
			}
		}
		else
		{
			backtrack(wordPos, matchPos);
		}
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	// word to find
	getline(cin, a);
	// string in which to find a
	getline(cin, b);
	n = a.length();
	m = b.length();

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

	build_table();
	kmp_search();

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