Mai intai trebuie sa te autentifici.
Cod sursa(job #2800850)
Utilizator | Data | 14 noiembrie 2021 10:10:44 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.74 kb |
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 2e6 + 5;
char a[N], b[N];
int lps[N];
int main() {
ifstream cin("strmatch.in");
ofstream cout("stramatch.out");
cin >> (a + 1) >> (b + 1);
cin.close();
int n = strlen(a + 1), m = strlen(b + 1);
int j = 0;
for (int i = 2; i <= n; ++i) {
while (j > 0 && a[i] != a[j + 1])
j = lps[j];
if (a[i] == a[j + 1])
++j;
lps[i] = j;
}
j = 0;
vector<int> ans;
for (int i = 1; i <= m; ++i) {
while (j > 0 && b[i] != a[j + 1])
j = lps[j];
if (b[i] == a[j + 1])
++j;
if (j == n)
ans.push_back(i - j);
}
cout << ans.size() << "\n";
for (auto i : ans)
cout << i << " ";
cout.close();
return 0;
}