Nu aveti permisiuni pentru a descarca fisierul grader_test2.in
Cod sursa(job #1891950)
| Utilizator | Data | 24 februarie 2017 14:40:36 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 26 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.33 kb |
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_STR 2000005
using namespace std;
auto fin = fopen("strmatch.in", "r");
auto fout = fopen("strmatch.out", "w");
char a[MAX_STR], b[MAX_STR];
unsigned int lena, lenb;
vector<int> matches;
void input() {
fscanf(fin, "%s", a);
fscanf(fin, "%s", b);
lena = strlen(a);
lenb = strlen(b);
}
void output() {
fprintf(fout, "%d\n", matches.size());
for (auto match: matches)
fprintf(fout, "%d ", match);
}
vector<int> getPrefix(const char* s, unsigned int lens) {
vector<int> res;
res.reserve(lens + 1);
res.push_back(-1);
auto k = -1;
for (auto i = 1u; i <= lens; ++i) {
while (k != -1 && s[k] != s[i - 1])
k = res[k];
k += 1;
res.push_back(k);
}
return res;
}
void solve() {
matches.reserve(1024);
auto pref = getPrefix(a, lena);
auto k = 0, i = 0;
while (i <= lenb - lena) {
if (a[k] == b[i + k])
++k;
else {
i += k - pref[k];
k = max(pref[k], 0);
}
if (k == lena) {
matches.push_back(i);
i += k - pref[k];
k = max(pref[k], 0);
}
}
}
int main() {
input();
solve();
output();
return 0;
}
