Pagini recente » Cod sursa (job #1957797) | Cod sursa (job #1440481) | Cod sursa (job #2384248) | Cod sursa (job #1174262) | Cod sursa (job #3217760)
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string.h>
const int32_t MAX_LEN = 2000000;
char str1[MAX_LEN + 1], str2[MAX_LEN + 1];
int32_t table[MAX_LEN], res[MAX_LEN];
int main() {
std::ifstream fin("strmatch.in");
std::ofstream fout("strmatch.out");
fin >> str1 >> str2;
int32_t len1 = strnlen(str1, MAX_LEN);
int32_t len2 = strnlen(str2, MAX_LEN);
int32_t cnd = 0;
table[0] = -1;
for(int32_t i = 1; i != len1; ++i, ++cnd) {
if(str1[i] == str1[cnd]) {
table[i] = table[cnd];
} else {
table[i] = cnd;
while(cnd >= 0 && str1[i] != str1[cnd])
cnd = table[cnd];
}
}
table[len1] = cnd;
int32_t len = 0, count = 0;
for(int32_t i = 0; i != len2;) {
if(str2[i] == str1[len]) {
++len;
++i;
if(len == len1) {
res[count++] = i - len;
len = table[len];
}
} else {
len = table[len];
if(len == -1) {
++i;
len = 0;
}
}
}
fout << count << '\n';
for(int32_t i = 0; i != count; ++i)
fout << res[i] << ' ';
fin.close();
fout.close();
return 0;
}