Mai intai trebuie sa te autentifici.
Cod sursa(job #2226033)
Utilizator | Data | 29 iulie 2018 11:34:51 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 14 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.12 kb |
#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 < llu > 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*=128;
}
//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*=128;
}
prime/=128;
for(int i=la; i<lb; i++)
{
//cout<<hashValueB<<endl;
if(hashValueB==hashValueA)
q.push(i-la);
hashValueB-=(b[i-la]-'A'+1);
hashValueB/=128;
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();
}
}