Pagini recente » Cod sursa (job #2386394) | Cod sursa (job #1097960) | Cod sursa (job #874709) | Cod sursa (job #2228391) | Cod sursa (job #1580956)
/**
* Worg
*/
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
const int MAX_LEN = 1 + 2000000;
const long long P1 = 1000000007;
const long long P2 = 1000000009;
const long long BASE = 67;
unsigned long long pow(unsigned long long base, unsigned long long exp, unsigned long long P) {
unsigned long long answer = 1, aux = base;
for(unsigned long long i = 1; i <= exp; i *= 2) {
if(i & exp) {
answer = (answer * aux) % P;
}
aux = (aux * aux) % P;
}
return answer;
}
const long long INV_BASE_1 = pow(BASE, P1 - 2, P1);
const long long INV_BASE_2 = pow(BASE, P2 - 2, P2);
int val(char c) {
if('A' <= c && c <= 'Z') {
return c - 'A';
}
if('a' <= c && c <= 'z') {
return 26 + c - 'a';
}
return 52 + c - '0';
}
struct Hash {
long long r1, r2;
int len;
Hash() {
this->r1 = this->r2 = this->len = 0;
}
bool operator ==(const Hash &other) const {
return (this->r1 == other.r1 &&
this->r2 == other.r2 &&
this->len == other.len);
}
};
Hash push_back(Hash h, char c) {
Hash answer;
answer.r1 = (h.r1 * BASE + val(c)) % P1;
answer.r2 = (h.r2 * BASE + val(c)) % P2;
answer.len = h.len + 1;
return answer;
}
Hash pop_front(Hash h, char c) {
Hash answer;
answer.r1 = (h.r1 - val(c) * pow(BASE, h.len - 1, P1) + BASE * P1) % P1;
answer.r2 = (h.r2 - val(c) * pow(BASE, h.len - 1, P2) + BASE * P2) % P2;
answer.len = h.len - 1;
return answer;
}
Hash getHash(char *s) {
Hash answer;
while(*s != '\0') {
answer = push_back(answer, *s);
s++;
}
return answer;
}
char P[MAX_LEN], T[MAX_LEN];
vector <int> sol;
int main() {
gets(P); gets(T);
int len1 = strlen(P), len2 = strlen(T);
Hash h1 = getHash(P), h2;
for(int i = 0; i < min(len2, len1); i++) {
h2 = push_back(h2, T[i]);
}
if(h1 == h2) {
sol.push_back(0);
}
//printf("%lld %lld %d\n", h1.r1, h1.r2, h1.len);
//printf("%lld %lld %d\n", h2.r1, h2.r2, h2.len);
for(int i = len1; i < len2 && sol.size() < 1000; i++) {
h2 = push_back(h2, T[i]);
h2 = pop_front(h2, T[i - len1]);
//printf("%lld %lld %d\n", h2.r1, h2.r2, h2.len);
if(h1 == h2) {
sol.push_back(i - len1 + 1);
}
}
printf("%d\n", (int)sol.size());
for(int ind : sol) {
printf("%d ", ind);
}
}