Pagini recente » Cod sursa (job #3269179) | Cod sursa (job #1069687) | Cod sursa (job #2395033) | Cod sursa (job #3258687) | Cod sursa (job #2886523)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int N, M, hash1, hash2, base=23, pw;
string A, B;
vector<int> sol;
int main()
{
fin>>A>>B;
N=A.size();
M=B.size();
if(N>M){
fout<<0;
return 0;
}
for(int i=0;i<N;i++){
hash1=hash1*base+A[i];
hash2=hash2*base+B[i];
}
pw=1;
for(int i=1;i<N;i++)
pw=pw*base;
if(hash1==hash2)
sol.push_back(0);
for(int i=N;i<M;i++){
hash2=(hash2-B[i-N]*pw)*base+B[i];
if(hash1==hash2)
sol.push_back(i-N+1);
}
fout<<sol.size()<<'\n';
int L=min(1000,(int)sol.size());
for(int i=0;i<L;i++)
fout<<sol[i]<<' ';
fin.close();
fout.close();
}