Cod sursa(job #2469716)

Utilizator davidcotigacotiga david davidcotiga Data 7 octombrie 2019 21:32:42
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <string.h>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");


int rez, v[1000], k;

void computeLPSArray(char* pat, int M, int* lps);

void KMPSearch(char* pat, char* txt)
{
	int M = strlen(pat);
	int N = strlen(txt);


	int lps[2000000];


	computeLPSArray(pat, M, lps);

	int i = 0;
	int j = 0;
	while (i < N) {
		if (pat[j] == txt[i]) {
			j++;
			i++;
		}

		if (j == M) {
			++rez;
			if (k <= 1000) {
				v[k] = i - j;
				++k;
			}
			j = lps[j - 1];
		}

		else if (i < N && pat[j] != txt[i]) {
			if (j != 0)
				j = lps[j - 1];
			else
				i = i + 1;
		}
	}
}

void computeLPSArray(char* pat, int M, int* lps)
{
	int len = 0;
	lps[0] = 0;

	int i = 1;
	while (i < M) {
		if (pat[i] == pat[len]) {
			len++;
			lps[i] = len;
			i++;
		}
		else
		{
			if (len != 0) {
				len = lps[len - 1];

			}
			else
			{
				lps[i] = 0;
				i++;
			}
		}
	}
}

int main() {
	char pat[2000000], txt[2000000];
	cin >> pat;
	cin >> txt;
	KMPSearch(pat, txt);
	cout << rez << "\n";
	for (int i = 0; v[i] != 0 && i < 1000; ++i)
		cout << v[i] << " ";

	return 0;

}