Pagini recente » Cod sursa (job #55581) | Cod sursa (job #2825688) | Cod sursa (job #821509) | Cod sursa (job #2522158) | Cod sursa (job #3220356)
#include <iostream>
#include <fstream>
#include <stdint.h>
#include <string.h>
const int32_t MAX_LEN = 2000000;
const int32_t MAX_OUT = 1000;
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 pos = 0, count = 0;
for(int32_t i = 0; i != len2;) {
if(str2[i] == str1[pos]) {
++pos;
++i;
if(pos == len1) {
res[count++] = i - pos;
pos = table[pos];
}
} else {
pos = table[pos];
if(pos == -1) {
++i;
pos = 0;
}
}
}
fout << count << '\n';
for(int32_t i = 0; i != count && i != MAX_OUT; ++i)
fout << res[i] << ' ';
fin.close();
fout.close();
return 0;
}