Pagini recente » Cod sursa (job #1144875) | Cod sursa (job #2615671) | Cod sursa (job #990863) | Cod sursa (job #187586) | Cod sursa (job #2142042)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
vector<int> sol;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int base=3,shift=1;;
string a,b;
in>>a>>b;
in.close();
int n=a.size();
ull hasha=0,hashb=0;
for(int i = 0 ; i <n;i++)
{
hasha+=a[i]*pow(3,i);
hashb+=b[i]*pow(3,i);
shift*=3;
}
shift/=3;
if(hasha==hashb)
{
sol.push_back(0);
}
for(int i = n ; i< b.size() ; i ++)
{
hashb-=b[i-n];
hashb/=3;
hashb+=b[i]*shift;
if(hasha == hashb)
{
sol.push_back(i-n+1);
}
}
out<<sol.size()<<'\n';
for(auto it:sol)
{
out<<it<<" ";
}
out.close();
}