Cod sursa(job #631652)

Utilizator Antonius74Antonius Cezar Hegyes Antonius74 Data 9 noiembrie 2011 13:12:41
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
using namespace std;
#define NMAX 2000

int T[NMAX];
char a[NMAX], b[NMAX];
void kmp_table();

int main()
{
	ifstream indata;
	indata.open("strmatch.in");
	ofstream outdata;
	outdata.open("strmatch.out");
	
	vector <int> pozitii;
	int m = 0, i = 0;
	
	indata.getline(b, NMAX);
	indata.getline(a, NMAX);
	
	kmp_table();

	while (i + m < strlen(a))
	{
		if (b[i] == a[m + i])
		{
			if (i == strlen(b) - 1)
			{
				pozitii.push_back(m);
				m = m + i - T[i];
				i = (T[i] > -1) ? T[i] : 0;
			}
			else
				i++;
		}
		else
		{
			m = m + i - T[i];
			i = (T[i] > -1) ? T[i] : 0;
		}
	}
	outdata<<pozitii.size()<<"\n";
	
	for (int i = 0; i < pozitii.size(); i++)
		outdata<<pozitii[i]<<" ";
}

void kmp_table()
{
	int pos = 2, cnd = 0;
	T[0] = -1;
	T[1] = 0;
	
	while (pos < strlen(b))
		if (b[pos - 1] == b[cnd])
		{
			cnd++;
			T[pos] = cnd;
			pos++;
		}
		else 
			if (cnd > 0)
				cnd = T[cnd];
			else
			{
				T[pos] = 0;
				pos++;
			}				
}