Cod sursa(job #2842572)

Utilizator alexdmnDamian Alexandru alexdmn Data 1 februarie 2022 10:36:47
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <fstream>
#include <queue>

using namespace std;
queue <int> q;
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");

    string s,a;
    long long int val1=0,val2=0,sum1=0,sum2=0,v1=0,v2=0,cnt=0,i;
    cin>>s>>a;

    for(i=0;i<s.size();i++)
	{
		sum1=0;
		sum2=0;
		sum1+=(s[i]-'A'+1);
		sum2=sum1;
		for(int j=i;j<s.size()-1;j++)
		{
			sum1*=27;
			sum2*=27;
			sum2%=666013;
			sum1%=1000000007;
		}
		val1+=sum1;
		val1%=1000000007;
		val2+=sum2;
		val2%=666013;
	}

    for(i=0;i<s.size();i++)
	{
		sum1=0;
		sum2=0;
		sum1+=(a[i]-'A'+1);
		sum2=sum1;
		for(int j=i;j<s.size()-1;j++)
		{
			sum1*=27;
			sum2*=27;
			sum2%=666013;
			sum1%=1000000007;
		}
		v1+=sum1;
		v1%=1000000007;
		v2+=sum2;
		v2%=666013;
	}
	if(v1==val1 && v2==val2)
	{
		q.push(0);
		cnt++;
	}

	for(i;i<a.size();i++)
	{
        sum1=0;
		sum2=0;
		sum1+=(a[i-s.size()]-'A'+1);
		sum2=sum1;
		for(int j=0;j<s.size()-1;j++)
		{
			sum1*=27;
			sum2*=27;
			sum2%=666013;
			sum1%=1000000007;
		}
		v1-=sum1;
		v2-=sum2;
		v1%=1000000007;
		v2%=666013;
		if(v1<0)
			v1+=1000000007;
		if(v2<0)
			v2+=666013;
		v1*=27;
		v2*=27;
		v1+=a[i]-'A'+1;
		v2+=a[i]-'A'+1;
		v1%=1000000007;
		v2%=666013;
		if(v1==val1 && v2==val2)
		{
			cnt++;
			if(q.size()<1000)
				q.push(i-s.size()+1);
		}
	}

	cout<<cnt<<'\n';

	while(!q.empty())
	{
        cout<<q.front()<<" ";
        q.pop();
	}

    return 0;
}