Cod sursa(job #2377129)

Utilizator HumikoPostu Alexandru Humiko Data 8 martie 2019 22:05:29
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

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

long long dp[2000005];
vector <int> ans;
string s;
string pat;
string txt;

void kmp(int n, int l) {
	int pos = 0;

	for (int i = 2; i < n; ++i) {
		dp[i] = dp[i - 1];
		while (dp[i] && s[i] != s[dp[i] + 1]) dp[i] = dp[dp[i]];
		if (s[i] == s[dp[i] + 1]) dp[i]++;
		if (dp[i] == l) {
			pos++;
			if (pos <= 1000) {
				ans.push_back(i-l-dp[i]-1);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);

	int n, l;

	fin >> pat;
	fin >> txt;

	s += '?';
	s += pat;
	s += '#';
	s += txt;
	
	l = pat.size();
	n = s.size();

	kmp(n, l);

	fout << ans.size() << '\n';
	for (auto x : ans) fout << x << " ";
}