Cod sursa(job #2880524)

Utilizator NFJJuniorIancu Ivasciuc NFJJunior Data 29 martie 2022 20:29:35
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#define cin f
#define cout g 
const int MOD = 1e9 + 7;
int main()
{
	string A, B;
	cin >> A >> B;
	int lenA = A.size(), lenB = B.size();
	if(lenA > lenB)
	{
		cout << 0;
		return 0;
	}
	int hashA = 0, P = 1;
	for(int i=0;i<lenA;i++)
	{
		hashA = (26 * hashA + A[i]) % MOD;
		if(i != 0)
			P = (P * 26) % MOD;
	}
	int hash = 0, k = 0, poz[1001];
	for(int i=0;i<lenA;i++)
		hash = (26 * hash + B[i]) % MOD;
	if(hash == hashA)
		poz[++ k] = 0;
	for(int i=lenA;i<lenB;i++)
	{
		hash = (26 * ((hash - B[i - lenA] * P + MOD) % MOD) + B[i]) % MOD;
		if(hash == hashA)
		{
			poz[++ k] = i - lenA + 1;
			if(k == 1000)
				break;
		}
	}
	cout<<k<<'\n';
	for(int i=1;i<=k;i++)
		cout<<poz[i]<<" ";
	return 0;
}