Pagini recente » Cod sursa (job #1155642) | Cod sursa (job #2482774) | Cod sursa (job #600858) | Cod sursa (job #2142924) | Cod sursa (job #2164611)
#include <iostream>
#include <fstream>
#include <array>
std::array<char, 2000000U> str;
std::array<char, 2000000U> fullstr;
std::array<int, 2000000U> prefixArray;
#include <cstring>
size_t prefixSize;
void Read()
{
std::ifstream f("strmatch.in");
f >> str.data();
f >> fullstr.data();
std::cout << str.data() << ' ' << fullstr.data() << '\n';
}
void MakePrefix()
{
size_t j = 0U, i;
prefixArray[0] = 0U;
for(i = 1U; str[i] != '\0'; ) {
if(str[i] == str[j]) {
prefixArray[i] = j + 1;
++i, ++j;
}
else if(j > 0U) {
j = prefixArray[j - 1];
}
else {
prefixArray[i] = 0;
++i;
}
}
prefixSize = i;
}
size_t nrap = 0U;
size_t offset = 0U;
std::ofstream g("strmatch.out");
std::array<size_t, 1000U> indexArray;
size_t lastIndex = 0U;
void FindIndex()
{
for(size_t i = 0U; fullstr[i] != '\0';) {
if(str[offset] == fullstr[i] && offset == prefixSize - 1U) {
++nrap;
if(lastIndex <= 1000U) {
indexArray[lastIndex++] = i - offset;
}
else
break;
if(offset > 0U)
offset = prefixArray[offset - 1U];
}
else if(str[offset] == fullstr[i]) {
++i;
++offset;
}
else if(offset > 0U) {
offset = prefixArray[offset - 1U];
}
else {
++i;
}
}
g << lastIndex << '\n';
for(size_t k = 0U; k < lastIndex; ++k) {
g << indexArray[k] << ' ';
}
}
void Solve()
{
MakePrefix();
}
int main()
{
Read();
Solve();
FindIndex();
/** std::cout << str.data() << '\n'; **/
/** std::cout << fullstr.data() << '\n'; **/
return 0;
}