Pagini recente » Cod sursa (job #280474) | Cod sursa (job #119227) | Cod sursa (job #2329467) | Cod sursa (job #2668323) | Cod sursa (job #1319623)
#include<fstream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define MAXN 2000005
#define P1 124567
#define P2 666013
using namespace std;
typedef long long var;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char WORD[MAXN];
var nrw;
var r1w, r2w, r1t, r2t;
vector<var> SOL;
var L1, L2, POW1, POW2;
int main() {
char c;
srand(time(NULL));
var i;
const var B1 = rand()%45 + 130;
const var B2 = rand()%45 + 163;
fin>>WORD;
POW1 = POW2 = 1;
nrw = strlen(WORD);
for(i=0; WORD[i]; i++) {
r1w = (r1w * B1 + WORD[i]) % P1;
L1 = POW1;
L2 = POW2;
POW1 = (POW1*B1)%P1;
POW2 = (POW2*B2)%P2;
r2w = (r2w * B2 + WORD[i]) % P2;
}
fin>>WORD;
for(i=0; i<nrw; i++) {
r1t = (r1t * B1 + WORD[i]) % P1;
r2t = (r2t * B2 + WORD[i]) % P2;
}
if(r1t == r1w && r2t == r2w) {
SOL.push_back(0);
}
var s=0;
var e = i;
for(; WORD[e]; e++, s++) {
r1t = (r1t - (WORD[s]*L1)%P1 + P1) % P1;
r2t = (r2t - (WORD[s]*L2)%P2 + P2) % P2;
r1t = (r1t * B1 + WORD[e]) % P1;
r2t = (r2t * B2 + WORD[e]) % P2;
if(r1t == r1w && r2t == r2w) {
SOL.push_back(s+1);
}
}
fout<<SOL.size()<<'\n';
for(i=0; i<SOL.size(); i++) {
fout<<SOL[i]<<" ";
}
return 0;
}