Mai intai trebuie sa te autentifici.
Cod sursa(job #582299)
| Utilizator | Data | 15 aprilie 2011 10:38:40 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.2 kb |
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2000010;
int n, m, pi[N];
char p[N], t[N];
vector<int> rez;
void read() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(p + 1);
gets(t + 1);
}
void init() {
for (n = 1; p[n]; ++ n);
-- n;
for (m = 1; t[m]; ++ m);
-- m;
}
void calc_pi() {
int q = 0;
pi[1] = 0;
for (int i = 2; i <= n; ++ i) {
while(q && p[i] != p[q + 1])
q = pi[q];
if (p[i] == p[q + 1])
++ q;
pi[i] = q;
}
}
void solve() {
int q = 0;
for (int i = 1; i <= m; ++ i) {
while(q && t[i] != p[q + 1])
q = pi[q];
if (t[i] == p[q + 1])
++ q;
if (q == n) {
rez.push_back(i - n);
if (rez.size() == 1000)
break;
q = pi[q];
}
}
}
void afis() {
printf("%d\n", rez.size());
for (int i = 0; i < rez.size(); ++ i)
printf("%d ", rez[i]);
printf("\n");
}
int main() {
read();
init();
calc_pi();
solve();
afis();
return 0;
}
