Pagini recente » Cod sursa (job #984856) | Cod sursa (job #3334631) | Cod sursa (job #2024445) | Cod sursa (job #3303537) | Cod sursa (job #2244489)
#include <fstream>
#include <string>
using namespace std;
#define MAX_STR 2000000
#define MAX_FINDS 1001
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
string pattern, str;
int numApp, map[MAX_STR], apps[MAX_FINDS];
void buildSufPref() {
int i, j, len = (int)pattern.size();
for (i = 1, j = 0; i < len; ++i) {
while (pattern[i] != pattern[j] && j) {
j = map[j - 1];
}
if (pattern[i] == pattern[j]) {
++j;
}
map[i] = j;
}
}
int main() {
fin >> pattern >> str;
int strLen = (int)str.size();
int pattLen = (int)pattern.size();
if (pattLen > strLen) {
fout << 0 << '\n';
return 0;
}
buildSufPref();
for (int i = 0, j = 0; i < strLen; ++i) {
while (j && pattern[j] != str[i]) {
j = map[j - 1];
}
if (str[i] == pattern[j]) {
++j;
}
if (j == pattLen) {
if (++numApp < MAX_FINDS) {
apps[numApp] = i - pattLen + 1;
}
j = map[j - 1];
}
}
fout << numApp << '\n';
numApp = (numApp > 1000 ? 1000 : numApp);
for (int i = 1; i <= numApp ; ++i) {
fout << apps[i] << ' ';
}
fout << '\n';
return 0;
}