Pagini recente » Cod sursa (job #729194) | Cod sursa (job #2931116) | Clasamentul arhivei de probleme | Cod sursa (job #2165016) | Cod sursa (job #2142408)
#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;
int ans=0;
if(hasha==hashb)
{
sol.push_back(0);
ans++;
}
for(int i = n ; i< b.size() ; i ++)
{
hashb-=b[i-n];
hashb/=3;
hashb+=b[i]*shift;
if(hasha == hashb)
{
ans++;
if(ans<=1000)
sol.push_back(i-n+1);
}
}
out<<sol.size()<<'\n';
for(int i = 0 ; i < 1000 ; i++)
{
out<<sol[i]<<" ";
}
out.close();
}