Cod sursa(job #1405083)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 28 martie 2015 20:28:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <string>
using namespace std;

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

void build_table(string word)
{
	int pos = 2, cnd = 0;
	t[0] = -1;
	t[1] = 0;
	
	while (pos < word.length())
	{
		if (word[pos - 1] == word[cnd])
		{
			cnd++;
			t[pos] = cnd;
			pos++;
		}
		else
			if (cnd > 0)
			{
				cnd = t[cnd];
			}
			else
			{
				t[pos] = 0;
				pos++;
			}
	}
}

void backtrack(int& wPos, int& mPos)
{
	if (t[wPos] > -1)
	{
		mPos += wPos - t[wPos];
		wPos = t[wPos];
	}
	else
	{
		wPos = 0;
		mPos++;
	}
}

void kmp_search(string word, string text)
{
	int matchPos = 0, wordPos = 0;

	while (matchPos + wordPos < text.length())
	{
		if (word[wordPos] == text[matchPos + wordPos])
		{
			// found a match of word in text
			if (wordPos == word.length() - 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);

	build_table(a);
	kmp_search(a, b);

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