Pagini recente » Cod sursa (job #2274143) | Cod sursa (job #2973702) | Cod sursa (job #2500136) | Cod sursa (job #910736) | Cod sursa (job #3236151)
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream in ("strmatch.in"); ofstream out ("strmatch.out");
char s1[2000001], s2[2000001];
int lgS1, lgS2;
int nrS1mod1, nrS1mod2, p1, p2, nrS2mod1, nrS2mod2;
char v[2000001];
int main(){
in >> s1 >> s2;
lgS1 = strlen(s1);
lgS2 = strlen(s2);
if (lgS1 > lgS2){
out << 0; return 0;
}
else{
p1 = p2 = 1;
for(int i = 0; i < lgS1; i++){
nrS1mod1 = (nrS1mod1 * 77 + s1[i])% MOD1;
nrS1mod2 = (nrS1mod2 * 77 + s1[i])% MOD2;
if (i!=0)
p1 = (p1 * 77) % MOD1, p2 = (p2 * 77) % MOD2;
}
for (int i = 0; i < lgS1; i++){
nrS2mod1 = (nrS2mod1 * 77 + s2[i]) % MOD1;
nrS2mod2 = (nrS2mod2 * 77 + s2[i]) % MOD2;
}
int cnt = 0;
if(nrS2mod1 == nrS1mod1 && nrS2mod2 == nrS1mod2){
v[0] = 1;
cnt++;
}
for(int i = lgS1; i < lgS2; i++){
nrS2mod1 = ((nrS2mod1 - (s2[i-lgS1] * p1) % MOD1 + MOD1) * 77 + s2[i]) % MOD1;
nrS2mod2 = ((nrS2mod2 - (s2[i-lgS1] * p2) % MOD2 + MOD2) * 77 + s2[i]) % MOD2;
if(nrS2mod1 == nrS1mod1 && nrS2mod2 == nrS1mod2){
v[i-lgS1 + 1] = 1;
cnt++;
}
}
out << cnt << endl;
cnt = 0;
for(int i = 0; i < lgS2 && cnt < 1000; i++)
if(v[i] == 1){
cnt++;
out << i << " ";
}
}
in.close(); out.close();
return 0;
}