Pagini recente » Cod sursa (job #777092) | Cod sursa (job #449912) | Cod sursa (job #1605538) | Cod sursa (job #2597137) | Cod sursa (job #1184192)
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#define SIZE 2000005
#define MOD 101
//68174081
using namespace std;
char a[SIZE], b[SIZE];
unsigned la, lb, hashv, rhashv, pow=1;
vector<int> sol;
int size = 1;
map<char, int> code;
void solve();
void init();
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){
printf("0\n");
return 0;
}
init();
solve();
printf("%d\n", sol.size());
for (unsigned i=0; i<sol.size() && i<1000; ++i){
printf("%d ", sol[i]);
}
return 0;
}
void init(){
for (char c='0'; c<='9'; ++c)
code[c] = size++;
for (char c='A'; c<='Z'; ++c)
code[c] = size++;
for (char c='a'; c<='z'; ++c)
code[c] = size++;
}
void solve(){
for (unsigned i=0; i<la; ++i){
hashv = (hashv*size+code[a[i]])%MOD;
rhashv = (rhashv*size+code[b[i]])%MOD;
}
for (unsigned i=1; i<la; ++i){
pow = pow*size%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*code[b[i-la]])%MOD)%MOD;
rhashv = (rhashv*size+code[b[i]])%MOD;
}
}