Pagini recente » Cod sursa (job #793604) | Cod sursa (job #364068) | Cod sursa (job #2357145) | Cod sursa (job #2120140) | Cod sursa (job #1404498)
#include <fstream>
#include <iostream>
#include <vector>
const int MAX_SIZE(2000001);
int Border [MAX_SIZE], Match;
char a [MAX_SIZE], b [MAX_SIZE];
std::vector<int> v;
inline void Read (void)
{
std::ifstream input("strmatch.in");
input >> a >> b;
input.close();
}
inline void Print (void)
{
std::ofstream output("strmatch.out");
output << Match << '\n';
for (unsigned int i(0) ; i < v.size() ; ++i)
output << v[i] << ' ';
output.put('\n');
output.close();
}
inline void KMP (void)
{
Border[0] = -1;
int i(0), j(-1);
while (a[i])
{
while (j >= 0 && a[i] != a[j])
j = Border[j];
++i;
++j;
Border[i] = j;
}
i = j = 0;
while (b[i])
{
while (j >= 0 && b[i] != a[j])
j = Border[j];
++i;
++j;
if (!a[j])
{
++Match;
if (Match <= 1000)
v.push_back(i - j);
j = Border[j];
}
}
}
int main (void)
{
Read();
KMP();
Print();
return 0;
}