Pagini recente » Monitorul de evaluare | Cod sursa (job #1510145) | Cod sursa (job #2760688) | Cod sursa (job #3200720) | Cod sursa (job #2226030)
#include <bits/stdc++.h>
#define MAX 4000000
#define llu long long unsigned int
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
queue < int > q;
map < llu , llu > myMap;
int main()
{
f>>a>>b;
llu la = a.size();
llu lb = b.size();
llu prime=1;
llu hashValueA = 0;
for(int i=0; i<la; i++)
{
int ascii = a[i]-'A'+1;
hashValueA+=ascii*prime;
prime*=3;
}
//cout<<hashValueA<<endl;
llu c=0;
llu hashValueB=0;
prime=1;
for(int i=0; i<la; i++)
{
hashValueB+=(b[i]-'A'+1)*prime;
prime*=3;
}
prime/=3;
for(int i=la; i<lb; i++)
{
//cout<<hashValueB<<endl;
if(hashValueB==hashValueA)
q.push(i-la);
hashValueB-=(b[i-la]-'A'+1);
hashValueB/=3;
hashValueB+=(b[i]-'A'+1)*prime;
}
//cout<<hashValueB<<endl;
if(hashValueA==hashValueB)
q.push(lb-la);
g<<q.size()<<'\n';
while(!q.empty())
{
llu x = q.front();
g<<x<<" ";
q.pop();
}
}