Mai intai trebuie sa te autentifici.
Cod sursa(job #2888682)
Utilizator | Data | 11 aprilie 2022 18:57:21 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.97 kb |
#include <bits/stdc++.h>
using namespace std;
string a, b;
int z[(int)4e6 + 5], ans[1001];
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
cin >> a >> b;
b = a + '|' + b;
int l, r;
l = r = 0;
for(int i = 1 ; i < b.size () ; ++ i)
{
if (i <= r)
{
z[i] = min (z[i - l], r - i + 1);
}
while (i + z[i] < b.size () && b[z[i]] == b[i + z[i]])
{
++z[i];
}
if (i + z[i] - 1 > r)
{
r = i + z[i] - 1;
l = i;
}
}
int cnt (0);
for(int i = a.size () + 1 ; i < b.size (); ++ i)
{
if (z[i] == a.size ())
{
++cnt;
if (cnt <= 1000)
ans[cnt] = i - a.size () - 1;
}
}
cout << cnt << '\n';
for(int i = 1 ; i <= min (1000, cnt) ; ++ i)
{
cout << ans[i] << ' ';
}
return 0;
}