Cod sursa(job #1405187)

Utilizator R4DIC4LTeodorescu Oana Maria R4DIC4L Data 28 martie 2015 22:14:42
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 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)
	{
		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);
	//fgets(a, sizeof(a), stdin);
	scanf("\n");
	// string in which to find a
	getline(cin, b);
	//fgets(b, sizeof(b), stdin);
	n = a.size();
	/*for (n = 0; a[n]; n++);
	n--;*/
	m = b.size();
	/*for (m = 0; b[m]; m++);
	m--;*/

	/*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;
}