Cod sursa(job #2765274)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 26 iulie 2021 04:00:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
 
int main() {
	string s1, s2;
	f >> s2 >> s1;
	int n1 = s1.length(), n2 = s2.length();
	int table[n2] = {0};
	table[0] = -1;
	int maxLength = 1;
	// Preparing Knuth–Morris–Pratt table
	for (int i = 1; i < n2; i++) {
		if (table[i-1] > -1 && s2[i] == s2[table[i-1] + 1]) {
			table[i] = table[i-1] + 1;
			maxLength = maxLength > table[i] ? maxLength : table[i];
		} else if (s2[i] == s2[0]) {
			table[i] = 0;
		} else {
			table[i] = -1;
		}
	}
	int i = 0, j = -1, count = 0;
	vector<int> results;
	
	while (i < n1) {
		if (j == n2 - 1) {
			if (results.size() < 1000)
				results.push_back(i - j - 1);
			count++;
			j = table[j];
		} else {
			if (s1[i] == s2[j+1]) {
				i++;
				j++;
			} else if (j > -1) {
				j = table[j];
			} else {
				i++;
			}
		}
	}
	if (j == n2 - 1) {
		if (results.size() < 1000)
			results.push_back(i - j - 1);
		count++;
	}
	g << count << "\n";
	for (int i = 0; i < results.size(); i++)
		g << results[i] << " ";
	return 0;
}