Pagini recente » Cod sursa (job #768170) | Monitorul de evaluare | Cod sursa (job #1409238) | Cod sursa (job #2899240) | Cod sursa (job #2244476)
#include <fstream>
#include <string>
using namespace std;
#define MAX_STR 2000000
#define MAX_FINDS 1000
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
string pattern, str;
int numApp, map[MAX_STR], apps[MAX_FINDS + 1];
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]) {
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 && numApp < MAX_FINDS; ++i) {
while (j && pattern[j] != str[i]) {
j = map[j - 1];
}
if (str[i] == pattern[j]) {
++j;
}
if (j == pattLen) {
apps[++numApp] = i - pattLen + 1;
j = map[j - 1];
}
}
fout << numApp << '\n';
for (int i = 1; i <= numApp ; ++i) {
fout << apps[i] << ' ';
}
fout << '\n';
return 0;
}