Pagini recente » Cod sursa (job #2057464) | Cod sursa (job #561483) | Cod sursa (job #488153) | Cod sursa (job #2483302) | Cod sursa (job #2852880)
#include <fstream>
#include <vector>
using namespace std;
ifstream file_in("strmatch.in");
ofstream file_out("strmatch.out");
size_t i, j, CNT;
vector<size_t> AP;
void Init_LPS(string PAT, size_t M, size_t* LPS)
{
size_t LEN = 0;
LPS[LEN] = 0;
i = 1;
while (i < M)
{
if (PAT[LEN] == PAT[i]) ++LEN, LPS[i++] = LEN;
else if (LEN) LEN = LPS[LEN - 1];
else LPS[i++] = 0;
}
}
void KMP(string PAT, string TXT)
{
size_t M = PAT.length();
size_t N = TXT.length();
size_t* LPS = new size_t[M];
Init_LPS(PAT, M, LPS);
i = 0, j = 0;
while (i < N)
{
if (TXT[i] == PAT[j]) ++i, ++j;
if (j == M)
{
++CNT;
AP.push_back(i - j);
j = LPS[j - 1];
}
else if (i < N && TXT[i] != PAT[j])
{
if (j) j = LPS[j - 1];
else ++i;
}
}
}
int main()
{
string A, B;
file_in >> A >> B;
KMP(A, B);
file_out << CNT << '\n';
for (auto it : AP) file_out << it << ' ';
return 0;
}