Cod sursa(job #2306468)

Utilizator KaryamKaryam Ahmad Karyam Data 22 decembrie 2018 13:35:48
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
using namespace std;

vector <int> compute_lps(string pattern) {
	int m = (int)pattern.length();
	vector <int> lps (m);
	lps[0] = 0;

	for (int i = 1; i < m; ++ i) {
			int j = lps[i-1];
			while (j > 0 && pattern[i] != pattern[j]) {
 				j = lps[j];
      }
			if (pattern[i] == pattern[j]) ++ j;
			lps[i] = j;
 }
	return lps;
}

void KMP(string pattern, string text){
	int n = (int)text.length();
	int m = (int)pattern.length();

	vector <int> lps = compute_lps(pattern);

	int i = 0, j = 0, app = 0, pos[1002];

	while (i < n) {
		while (j < m && i < n && text[i] == pattern[j])
			i++, j++;

		if (j == m && app < 1e3) {
			pos[app] = i - m;
			app ++;
			j = lps[j-1];
		}
		else if(i < n && pattern[j] != text[i]){
			if(j != 0)
				j = lps[j-1];
			else ++i;
		}
	}

	printf("%d\n", app);
	for(int i = 0; i < app; ++ i)
		printf("%d ", pos[i]);
}

int main(){
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	string text;
  string pattern;

  cin >> pattern;
	cin >> text;

	KMP(pattern, text);
	return 0;
}