Pagini recente » Cod sursa (job #2625286) | Cod sursa (job #441061) | Cod sursa (job #327255) | Cod sursa (job #977492) | Cod sursa (job #1114126)
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define nmax 2000005
using namespace std;
int k,n;
char a[nmax],b[nmax];
int ha,hb[nmax];
const int p = 13,mod = 666013;
vector <int> r;
queue <int> q;
int sum,nr;
int putere(int b,int p) {
if (p==1) return b;
int put = putere(b,p/2);
if (p%2==0) return put*put;
else return put*put*b;
}
int hash(char x) {
x = x-'A';
if (q.size() > k) {
sum -= q.front() * putere(p,k);
q.pop();
}
sum *=p;
sum %= mod;
q.push(x);
sum += p*x;
sum %= mod;
return sum;
}
bool check(int s) {
int bun = true;
for (int i=0;i<k;i++) if (a[i] != b[i+s]) bun = false;
if (bun) r.insert(r.begin(),s);
return bun;
}
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",a,b);
k = strlen(a);
n = strlen(b);
for (int i=1;i<=n;i++) {
hb[i] = hash(b[i]);
}
for (int i=1;i<=k;i++) ha = hash(k);
for (int i=1;i<=n-k;i++) if (check(i)) nr++;
printf("%d\n",nr);
while (!r.empty()) {
printf("%d ",r.back());
r.pop_back();
}
return 0;
}