Cod sursa(job #3304065)
| Utilizator | Data | 20 iulie 2025 11:27:24 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.49 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int n, m, ans;
string a, b;
int lps[2000005];
vector<int> poz;
void build_lps()
{
int len = 0;
int i = 2;
while(i <= n)
{
if(a[i] == a[len + 1])
{
len++;
lps[i] = len;
i++;
}
else
{
if(len != 0)
{
len = lps[len];
}
else
{
lps[i] = 0;
i++;
}
}
}
}
int main()
{
in>>a>>b;
n = a.size();
m = b.size();
a = '$' + a;
b = '$' + b;
build_lps();
// for(int i = 1; i<=n; i++)
// {
// out<<lps[i]<<" ";
// }
int i = 0;
int j = 1;
while(j <= m)
{
if(b[j] == a[i + 1])
{
j++;
i++;
if(i == n)
{
ans++;
if(poz.size() < 1000)
{
poz.push_back(j - 1);
}
i = lps[i];
}
}
else
{
if(i == 0)
{
j++;
}
else
{
i = lps[i];
}
}
}
out<<ans<<'\n';
for(auto it: poz)
{
out<<it - n<<" ";
}
return 0;
}
