Pagini recente » Cod sursa (job #1341506) | Cod sursa (job #620317) | Cod sursa (job #1117495) | Cod sursa (job #1044762) | Cod sursa (job #2143077)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
vector<int> sol;
const int x=47,y=73;
#define mod 666
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int shift1=1,shift2=1;
string a,b;
in>>a>>b;
in.close();
int n=a.size();
ull hasha1=0,hashb1=0,hasha2=0,hashb2=0;
for(int i = 0 ; i <n;i++)
{
if(i!=0){
shift1*=x;
shift2*=y;
}
hasha1+=a[i]*shift1;
hasha2+=a[i]*shift2;
hashb1+=b[i]*shift1;
hashb2+=b[i]*shift2;
}
if(hasha1==hashb1 && hasha2==hashb2)
{
sol.push_back(0);
}
for(int i = n ; i< b.size() ; i ++)
{
hashb1-=b[i-n];
hashb1/=x;
hashb1+=b[i]*shift1;
hashb2-=b[i-n];
hashb2/=y;
hashb2+=b[i]*shift2;
if(hasha1==hashb1 && hasha2==hashb2)
{
sol.push_back(i-n+1);
}
}
out<<sol.size()<<'\n';
int limit=min(1000,int(sol.size()));
for(int i = 0 ; i < limit ;i++)
{
out<<sol[i]<<" ";
}
out.close();
return 0;
}