Pagini recente » Cod sursa (job #1958135) | Cod sursa (job #2881335) | Cod sursa (job #2383859) | Cod sursa (job #299633) | Cod sursa (job #1182837)
#include <cstdio>
#include <cstring>
#include <vector>
#define SIZE 2000005
#define MOD 165191021
using namespace std;
char a[SIZE], b[SIZE];
unsigned la, lb, hashv, rhashv, pow=1;
vector<int> sol;
void solve();
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", a, b);
la = strlen(a);
lb = strlen(b);
if (la>lb){
return 0;
}
solve();
printf("%d\n", sol.size());
for (unsigned i=0; i<sol.size(); ++i){
printf("%d ", sol[i]);
}
return 0;
}
void solve(){
for (unsigned i=0; i<la; ++i){
hashv = (hashv*27+a[i]-'A'+1)%MOD;
pow = pow*27%MOD;
}
pow /= 27;
for (unsigned i=0; i<la; ++i){
rhashv = (rhashv*27+b[i]-'A'+1)%MOD;
}
for (unsigned i=la; i<=lb; ++i){
if (hashv==rhashv && !memcmp(a, &b[i-la], la)){
sol.push_back(i-la);
if (sol.size()>=1000)
return;
}
rhashv = (rhashv+MOD-pow*(b[i-la]-'A'+1))%MOD;
rhashv = (rhashv*27+b[i]-'A'+1)%MOD;
}
}