Pagini recente » Arbori de intervale si aplicatii in geometria computationala | Cod sursa (job #2752595) | Cod sursa (job #31976) | Istoria paginii utilizator/katalintaleent | Cod sursa (job #1976919)
/*
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;
int sol;
void ReadInput() {
ifstream f("strmatch.in");
f >> pattern + 1;
f >> arr + 1;
}
void ComputePrefix() {
int len = strlen(pattern+1);
int k = 0;
for (int i = 2; 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+1);
int lenarr = strlen(arr+1);
int k = 0;
for (int i = 1; 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) {
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;
}