Cod sursa(job #1552570)

Utilizator howsiweiHow Si Wei howsiwei Data 18 decembrie 2015 11:47:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 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;
		}
	}
	int nans = 0;
	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()) {
				if (nans < 1000) {
					ans.push_back(l);
				}
				nans++;
			}
		}
	}
	printf("%d\n", nans);
	for (int i = 0; i < ans.size(); i++) {
		printf("%d%c", ans[i], " \n"[i == ans.size()-1]);
	}
}