Pagini recente » Cod sursa (job #1554571) | Cod sursa (job #1957721) | Cod sursa (job #798108) | Cod sursa (job #1429632) | Cod sursa (job #1920659)
#include <cstdio>
#include <string.h>
#define BASE 73
#define MOD1 100007
#define MOD2 100021
char A[2000001], B[2000001];
int lengthA, lengthB;
bool match[2000001];
int hashA1, hashA2;
int power1 = 1, power2 = 1;
int hash1, hash2, matches;
int main(){
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
lengthA = strlen(A);
lengthB = strlen(B);
if(lengthA > lengthB){
printf("0");
return 0;
}
for(int i = 0; i < lengthA; i++){
hashA1 = (hashA1 * BASE + A[i]) % MOD1;
hashA2 = (hashA2 * BASE + A[i]) % MOD2;
if(i != 0){
power1 = (power1 * BASE) % MOD1;
power2 = (power2 * BASE) % MOD2;
}
}
for(int i = 0; i < lengthA; i++){
hash1 = (hash1 * BASE + B[i]) % MOD1;
hash2 = (hash2 * BASE + B[i]) % MOD2;
}
if(hash1 == hashA1 && hash2 == hashA2){
match[0] = true;
matches++;
}
for(int i = lengthA; i < lengthB; i++){
hash1 = ((hash1 - (B[i - lengthA] * power1) % MOD1 + MOD1) * BASE + B[i]) % MOD1;
hash2 = ((hash2 - (B[i - lengthA] * power2) % MOD2 + MOD2) * BASE + B[i]) % MOD2;
if(hash1 == hashA1 && hash2 == hashA2){
match[i - lengthA + 1] = true;
matches++;
}
}
printf("%d\n", matches); matches = 0;
for (int i = 0; i < lengthB && matches < 1000; i++){
if(match[i] == true){
matches++;
printf("%d ", i);
}
}
return 0;
}