Cod sursa(job #3151649)
| Utilizator | Data | 22 septembrie 2023 12:11:23 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.21 kb |
#include <fstream>
#include <vector>
#define pb push_back
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a , b;
int lps[2000001];
signed main()
{
cin >> a >> b;
int sza = a.size();
int szb = b.size();
for(int i = 0 , j = 1 ; j < sza ;)
{
if(a[i]==a[j])
{
lps[j] = lps[j-1]+1;
i++;
j++;
}
else
{
if(i) i = lps[i-1];
else j++;
}
}
vector <int> ans;
int hm = 0;
for(int i = 0 , j = 0 ; j < szb ;)
{
if(a[i]==b[j])
{
if(i<sza-1)
{
j++;
i++;
}
else
{
if(hm<1000)
{
hm++;
ans.pb(j-sza+1);
}
i = lps[sza-1];
j++;
}
}
else
{
if(i == 0)
{
j++;
}
else i = lps[i-1];
}
}
cout << ans.size() << '\n';
for(auto &it : ans) cout << it << ' ';
return 0;
}
