Cod sursa(job #2675182)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 21 noiembrie 2020 10:59:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

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

typedef string::const_iterator sit;

class Roller{
private:
	int a, n;
	int ap = 1;
	int q = 0;
public:
	Roller();
	Roller(int a, int n, sit lt, sit rt) : a(a), n(n){
		for(auto it = lt; it != rt; ++it){
			q *= a;
			q += *it;
			q %= n;
			
			if(it!=lt)ap *= a;
			ap %= n;
		}
	}
	Roller(int a, int n, const string &str) : Roller(a,n,str.begin(),str.end()){}
	Roller(int a, int n, const string &str, int len) : Roller(a,n,str.begin(),str.begin()+len){}
	void roll(char out, char in){
		q -= out*ap;
		q += n*128;
		q %= n;
		q *= a;
		q += in;
		q %= n;
	}
	bool operator==(const Roller &rhs){
		return q == rhs.q;
	}
};

const int a = 31;
const int n1 = 1000003, n2 = 1000033;

string pattern, text;

int ans1 = 0;
vector<int> ans2;

int main(){
	// ios_base::sync_with_stdio(false);
	fin >> pattern >> text;
	Roller rpattern[] = {Roller(a,n1,pattern),Roller(a,n2,pattern)};
	Roller rtext[] = {Roller(a,n1,text,pattern.size()),Roller(a,n2,text,pattern.size())};
	
	if(rpattern[0] == rtext[0] && rpattern[1] == rtext[1]){
		ans1++;
		if(ans1 <= 1000)ans2.push_back(0);
	}
	
	for(int i = pattern.size(); i < text.size(); ++i){
		rtext[0].roll(text[i-pattern.size()], text[i]);
		rtext[1].roll(text[i-pattern.size()], text[i]);
		if(rpattern[0] == rtext[0] && rpattern[1] == rtext[1]){
			ans1++;
			if(ans1 <= 1000)ans2.push_back(i-pattern.size()+1);
		}
	}
	
	fout << ans1 << "\n";
	for(auto a : ans2)fout << a << " ";
	return 0;
}