Pagini recente » Cod sursa (job #1111136) | Cod sursa (job #1452317) | Cod sursa (job #2432435) | Cod sursa (job #1502542) | Cod sursa (job #1379238)
#include <fstream>
const int MAX_SIZE(2000001);
const int MAX_M(1000);
char a [MAX_SIZE], b [MAX_SIZE];
int Border [MAX_SIZE];
int Total_matches, Matches [MAX_M];
inline void Read (void)
{
std::ifstream input("strmatch.in");
input >> a >> b;
input.close();
}
inline void Print (void)
{
std::ofstream output("strmatch.out");
output << Total_matches << '\n';
for (int i(0) ; i < Total_matches && i < MAX_M ; ++i)
output << Matches[i] << ' ';
output.put('\n');
output.close();
}
inline void KnuthMorrisPratt (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 && a[j] != b[i])
j = Border[j];
++i;
++j;
if (!a[j])
{
if (Total_matches < MAX_M)
Matches[Total_matches] = i - j;
++Total_matches;
j = Border[j];
}
}
}
int main (void)
{
Read();
KnuthMorrisPratt();
Print();
return 0;
}