Pagini recente » Cod sursa (job #1674072) | Cod sursa (job #1542508) | Cod sursa (job #69171) | Cod sursa (job #457759) | Cod sursa (job #2732413)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const int SOLMAX = 1000;
const int LMAX = 2000000;
string A;
string B;
int dp[1 + 2 * LMAX + 1];
vector<int> sol;
int sizeA;
void precalcPrefix()
{
dp[1] = 0;
int pi = 0;
for (int i = 2; i < A.size(); i++)
{
while (pi > 0 && A[i] != A[pi + 1])
{
pi = dp[pi];
}
if (A[i] == A[pi + 1])
pi++;
dp[i] = pi;
if (dp[i] == sizeA)
{
sol.emplace_back(i - sizeA - sizeA + 1 - 2);
}
}
}
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in >> A >> B;
sizeA = A.size();
A = ' ' + A + '$' + B;
precalcPrefix();
out << sol.size() << '\n';
for (int i = 0; i < min((int)sol.size(), SOLMAX); i++)
{
out << sol[i] << ' ';
}
return 0;
}