Pagini recente » Cod sursa (job #3151848) | Cod sursa (job #430183) | Cod sursa (job #971542) | Cod sursa (job #1809244) | Cod sursa (job #2732051)
#include <fstream>
#include <vector>
using namespace std;
const int LMAX = 2000000;
string A;
string B;
int prefix[1 + LMAX];
vector<int> sol;
// Indexat de la 1
void calcularePrefix()
{
int pi = 0;
prefix[1] = 0;
for (int i = 2; i < A.size(); i++)
{
while (pi > 0 && A[i] != A[pi + 1])
pi = prefix[pi];
if (A[i] == A[pi + 1])
++pi;
prefix[i] = pi;
}
}
void gasesteAparitii()
{
int pi = 0;
for (int i = 1; i < B.size(); i++)
{
while (pi > 0 && B[i] != A[pi + 1])
pi = prefix[pi];
if (B[i] == A[pi + 1])
++pi;
if (pi == A.size() - 1)
sol.emplace_back(i - A.size() + 2 - 1);
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> A >> B;
A = ' ' + A;
B = ' ' + B;
calcularePrefix();
gasesteAparitii();
out << sol.size() << '\n';
for (int i = 0; i < min((int)sol.size(), 1000); i++)
{
out << sol[i] << ' ';
}
return 0;
}