Pagini recente » Cod sursa (job #715220) | Cod sursa (job #3198687) | Cod sursa (job #239188) | Cod sursa (job #1459467) | Cod sursa (job #2231662)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a, b;
int la, lb;
queue < ll > q;
ll hashA, hashB;
ll hashValue(int u, int v, string x)
{
int hV=0;
for(int i=u; i<=v; i++)
hV+=(int)x[i];
return hV;
}
bool match(int start)
{
for(int i=0; i<la; i++)
if(a[i]!=b[start++])
return false;
return true;
}
int main()
{
/*for(char i='A'; i<='C'; i++)
cout<<(int)i<<endl;
cout<<endl;*/
f>>a>>b;
la = a.length();
lb = b.length();
hashA = hashValue(0, la-1, a);
hashB = hashValue(0, la-2, b);
//cout<<hashA<<" "<<hashB<<endl;
for(int i=la-1; i<lb; i++)
{
//cout<<"Punem "<<i<<endl;
hashB+=(int)b[i];
if(hashA==hashB)
if(match(i-la+1))
q.push(i-la+1);
hashB-=(int)b[i-la+1];
//cout<<"Scadem "<<i-la+1<<endl;
}
g<<q.size()<<'\n';
while(!q.empty())
{
int nr = q.front();
g<<nr<<" ";
q.pop();
}
}