Pagini recente » Cod sursa (job #28621) | Cod sursa (job #215448) | Cod sursa (job #166921) | Cod sursa (job #1595624) | Cod sursa (job #1976920)
/*
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];
int sol;
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) {
if (Sol.size() < 1000)
Sol.push_back(i - k);
++sol;
}
}
}
void PrintSolution() {
ofstream g("strmatch.out");
g << sol << '\n';
for (auto i : Sol)
g << i << ' ';
g << '\n';
}
void Solve() {
ReadInput();
ComputePrefix();
FindMatch();
PrintSolution();
}
int main()
{
Solve();
return 0;
}