Cod sursa(job #1552547)

Utilizator howsiweiHow Si Wei howsiwei Data 18 decembrie 2015 11:18:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	string a;
	cin >> a;
	string b;
	cin >> b;
	vector<int> c(a.size()+1);
	int l = 0;
	int r = 0;
	for (int i = 1; i <= a.size(); i++) {
		if (l+c[i-l] < r) {
			c[i] = l+c[i-l];
		} else {
			l = i;
			r = max(r, i);
			while (r < a.size() && a[r-l] == a[r]) r++;
			c[i] = r;
		}
	}
	vector<int> ans;
	l = 0;
	r = 0;
	for (int i = 0; i <= b.size(); i++) {
		if (l+c[i-l] < r) {
		} else {
			l = i;
			r = max(r, i);
			while (r-l < a.size() && r < b.size() && a[r-l] == b[r]) r++;
			if (r-l == a.size()) {
				ans.push_back(l);
			}
		}
	}
	printf("%d\n", ans.size());
	int np = min(1000u, ans.size());
	for (int i = 0; i < np; i++) {
		printf("%d%c", ans[i], " \n"[i == np-1]);
	}
}