Pagini recente » Cod sursa (job #697073) | Cod sursa (job #1943611) | Cod sursa (job #345257) | Cod sursa (job #1137096) | Cod sursa (job #2761524)
#include <fstream>
#include <vector>
#define NMAX 2000005
#define LIMIT 1000
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int lps[NMAX], fullAnswer;
string str, pat;
vector <int> answer;
void getKmp(string str, string pat) {
int i = 0;
int j = 0;
while (i < str.size()) {
if (str[i] == pat[j]) {
i++;
j++;
}
if (j == pat.size()) {
fullAnswer++;
if (answer.size() < LIMIT)
answer.push_back(i - j);
j = lps[j - 1];
} else {
if (i < str.size() && str[i] != pat[j]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
}
void getLps(string pat) {
int len = 0;
int i = 1;
lps[0] = 0;
while (i < pat.size()) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
int main()
{
f >> pat >> str;
getLps(pat);
getKmp(str, pat);
g << fullAnswer << "\n";
for (auto a : answer)
g << a << " ";
return 0;
}