Cod sursa(job #3147353)

Utilizator daristyleBejan Darius-Ramon daristyle Data 25 august 2023 21:46:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>

using namespace std;

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

const int STRLEN_MAX = 2e6;
const int POS_MAX = 1e3;
char pattern[STRLEN_MAX + 1], str[STRLEN_MAX + 1];
int lps[STRLEN_MAX], pos[POS_MAX], n = 0;

void PrecomputeLPS(const char* pattern){
	int i = 1, pefixLen;

	lps[0] = 0;
	while(pattern[i]){
		pefixLen = lps[i - 1];

		while(pefixLen && pattern[pefixLen] != pattern[i])
			pefixLen = lps[pefixLen - 1];

		if(pattern[pefixLen] == pattern[i])
			lps[i] = pefixLen + 1;
		else
			lps[i] = 0;

		++i;
	}
}

void KMP(const char* str, const char* pattern){
	PrecomputeLPS(pattern);

	int i = 0, j = 0;
	while(str[i]){
		if(pattern[j] == str[i]){
			++i, ++j;

			if(!pattern[j]){
				if(n < POS_MAX)
					pos[n] = i - j;
				n++;
				j = lps[j - 1];
			}
		}else{
			if(j > 0)
				j = lps[j - 1];
			else
				++i;
		}
	}
}

int main(){

	fin >> pattern >> str;

	KMP(str, pattern);

	fout << n << '\n';
	if(n > POS_MAX)
		n = POS_MAX;
	for(int i = 0; i < n; ++i)
		fout << pos[i] << ' ';
	fout.put('\n');

	fin.close();
	fout.close();
	return 0;
}