Cod sursa(job #2981717)

Utilizator mrvalentynPorumb Valentin mrvalentyn Data 18 februarie 2023 15:51:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int poz[2000000];
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++;
			}
		}
	}
}
void KMPSearch(char pat[], char txt[])
{
    int kap = 0;
    int contrp = 1;
	int M = strlen(pat);
	int N = strlen(txt);
	int lps[M];
	computeLPSArray(pat, M, lps);

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

		if (j == M) {
            kap++;
			//g << i - j << ' ';
			poz[contrp++] = i - j;
			j = lps[j - 1];
		}
		else if (i < N && pat[j] != txt[i]) {
			if (j != 0)
				j = lps[j - 1];
			else
				i = i + 1;
		}
	}
	g << kap << endl;
	for(int i = 1; i < contrp; ++i) g << poz[i] << ' ';
}

char a[2000000];
char b[2000000];


int main()
{
    f >> a;
    f >> b;

	KMPSearch(a, b);
	return 0;
}