Cod sursa(job #2842618)

Utilizator alexdmnDamian Alexandru alexdmn Data 1 februarie 2022 11:12:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <queue>
#define hash1 1000000007
#define hash2 666013

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=1,sum2=1,v1=0,v2=0,cnt=0,i;
    cin>>s>>a;

    for(i=0;i<s.size();i++)
	{
		val1=(val1*59+s[i])%hash1;
		val2=(val2*59+s[i])%hash2;
		v1=(v1*59+a[i])%hash1;
		v2=(v2*59+a[i])%hash2;
		if(i!=s.size()-1)
		{
			sum1*=59;
			sum1%=hash1;
			sum2*=59;
			sum2%=hash2;
		}
	}
	if(v1==val1 && v2==val2)
	{
		q.push(0);
		cnt++;
	}

	for(i;i<a.size();i++)
	{
		v1-=a[i-s.size()]*sum1;
		v2-=a[i-s.size()]*sum2;
		v1%=hash1;
		v2%=hash2;
		if(v1<0)
			v1+=hash1;
		if(v2<0)
			v2+=hash2;
		v1*=59;
		v2*=59;
		v1+=a[i];
		v2+=a[i];
		v1%=hash1;
		v2%=hash2;
		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;
}