Pagini recente » Cod sursa (job #2188614) | Cod sursa (job #154436) | Monitorul de evaluare | Cod sursa (job #33433) | Cod sursa (job #1976912)
/*
Keep It Simple!
*/
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int MAX_N = 2000005;
char arr[MAX_N],pattern[MAX_N];
int prefix_array[MAX_N];
vector<int> Sol;
void ReadInput() {
ifstream f("strmatch.in");
f >> pattern;
f >> arr;
}
void ComputePrefix() {
int len = strlen(pattern);
int k = -1;
for (int i = 1; i < len; ++i) {
while (k >= 0 && pattern[k+1] != pattern[i])
k = prefix_array[k];
if (pattern[k+1] == pattern[i]) ++k;
prefix_array[i] = k;
}
}
void FindMatch() {
int lenpat = strlen(pattern);
int lenarr = strlen(arr);
int k = -1;
for (int i = 0; i < lenarr; ++i) {
while (k >= 0 && pattern[k+1] != arr[i])
k = prefix_array[k];
if (pattern[k+1] == arr[i])
++k;
if (k == lenpat - 1)
Sol.push_back(i - k);
}
}
void PrintSolution() {
ofstream g("strmatch.out");
g << Sol.size() << '\n';
for (auto i : Sol)
g << i << ' ';
g << '\n';
}
void Solve() {
ReadInput();
ComputePrefix();
FindMatch();
PrintSolution();
}
int main()
{
Solve();
return 0;
}