Cod sursa(job #2668772)

Utilizator robertrRotaru Stefan Robert robertr Data 5 noiembrie 2020 12:32:25
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

string pat, txt;

const int d = 256, mod = 2000003;

set<int> sol;

void rabin_karp(string pat, string txt, int q) {
	int p = 0, t = 0, h = 1, j = 0;
	int m = pat.size();
	int n = txt.size();
	for(int i = 0; i < m - 1; ++i) {
		h = (h * d) % q;
	}
	for(int i = 0; i < m; ++i) {
		p = (d * p + pat[i]) % q;
		t = (d * t + txt[i]) % q;
	}
	for(int i = 0; i <= n - m; ++i) {
		if(p == t) {
			for(j = 0; j < m; ++j) {
				if(txt[i+j] != pat[j]) {
					break;
				}
			}
			if(j == m) {
				sol.insert(i);
			}
		}
		if(i < n - m) {
			t = (d * (t - txt[i]*h) + txt[i+m]) % q;
			if(t < 0) {
				t = (t+q);
			}
		}
	}
}

void read() {
	getline(f, pat);
	// f.get();
	getline(f, txt);
}

void solve() {
	read();
	rabin_karp(pat, txt, mod);
	g << sol.size() << '\n';
	for(int val : sol) {
		g << val << " ";
	}
	g << '\n';
}

int main(void) {
	solve();
}