Mai intai trebuie sa te autentifici.
Cod sursa(job #3291961)
| Utilizator | Data | 6 aprilie 2025 13:55:50 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.11 kb |
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2000001;
int L[2 * NMAX];
void ZAlgo(string &s, int lgPattern)
{
int counter = 0;
vector<int> pos;
L[0] = 1;
int best = 0;
for (int i = 1; i < s.size(); i++)
{
int rightBound = best + L[best];
int j = L[best] - (rightBound - i);
if (i < rightBound)
L[i] = min(L[j], rightBound - i);
while (i + L[i] < s.size() && s[L[i]] == s[i + L[i]])
{
L[i]++;
}
if (i + L[i] > rightBound)
{
best = i;
}
if (L[i] == lgPattern)
{
counter++;
if (counter <= 1000)
{
pos.push_back(i - lgPattern - 1);
}
}
}
g << counter << '\n';
for (auto p: pos)
{
g << p << ' ';
}
}
int main()
{
string A, B;
f >> A >> B;
/// A#B
string finalString = A;
finalString += "#";
finalString += B;
ZAlgo(finalString, A.size());
return 0;
}
