Cod sursa(job #2671335)

Utilizator davidcotigacotiga david davidcotiga Data 11 noiembrie 2020 22:21:27
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>
#include <map>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int lpsG[2000005];
int nrRez;
vector<int> rez;

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 M = strlen(pat);
	int N = strlen(txt);

	ComputeLPSArray(pat, M, lpsG);

	int i = 0;
	int j = 0;

	while (i < N) {
		if (pat[j] == txt[i]) {
			i++;
			j++;
		}
		if (j == M) {
			j = lpsG[j - 1];
			nrRez++;
			rez.push_back(i - j);
		}
		else if (i < N && pat[j] != txt[i]) {
			if (j != 0)
				j = lpsG[j - 1];
			else
				i++;
		}
	}
}

char pat[200005];
char txt[200005];

int main() {

	fin >> pat >> txt;

	KMPSearch(pat, txt);

	fout << nrRez << "\n";

	for (int i = 0; i < rez.size(); ++i)
		fout << rez[i] - 2 << " ";

	return 0;
}