Cod sursa(job #3311334)

Utilizator ViAlexVisan Alexandru ViAlex Data 21 septembrie 2025 12:40:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include<iostream>
#include<algorithm>
#include<fstream>
#include<vector>
using namespace std;

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


// a b c a b c a b a
// 0 0 0 1 2 3 4 5 
vector<int> lps(const string& pattern) {
	vector<int> result(pattern.length());
	int j = 0; // the length of the suffix.
	int i = 1;

	while (i < pattern.length()) {
		if (pattern[i] == pattern[j]) {
			j++;
			result[i] = j;
			i++;
		} else if (j==0) {
			result[i] = 0;
			i++;
		} else{
			j = result[j-1];
		}
	}

	return result;	
}

pair<vector<int>, int> kmp(const string& needle, const string& haystack) {
	vector<int> pattern = lps(needle);
	vector<int> matches;
	int i = 0, j = 0;
	int count = 0;

	while (i < haystack.length()) {
		if (needle[j] == haystack[i]) {
			i++;
			j++;
		} else if (j == 0) {
			i++;
		} else{
			j = pattern[j-1];
		}

		if ( j == needle.length()) {
			count++;
			if (count<=1000){
				matches.push_back(i - needle.length());
			}
			j = pattern[j-1];
		}
	}

	return {matches, count};
}

int main() {
	string a, b;
	in>>a>>b;

	auto matches = kmp(a, b);
	out<<matches.second<<endl;
	for (int x: matches.first) {
		out<<x<<' ';
	}
	return 0;
}