Pagini recente » Cod sursa (job #287881) | Cod sursa (job #880560) | Cod sursa (job #3152312) | Cod sursa (job #427505) | Cod sursa (job #2115542)
#include <fstream>
std::ofstream g("strmatch.out");
char substring[2000000], fullstring[2000000];
int i = 0, j = 1;
int length = 0;
int auxArray[2000000];
void Read()
{
std::ifstream f("strmatch.in");
f >> substring;
f >> fullstring;
}
void CompleteAuxArray()
{
while (substring[i] != NULL && substring[j] != NULL) {
if (substring[i] == substring[j]) {
auxArray[j] = i + 1;
i++;
j++;
}
else {
if (i >= 1) {
i = auxArray[i - 1];
}
else {
i = 0;
auxArray[j] = 0;
j++;
}
}
}
length = j;
}
void Substr()
{
int offset = 0;
int nrap = 0;
bool pattern = false;
for (i = 0; fullstring[i] != NULL; i++) {
if (fullstring[i] == substring[offset]) {
pattern = true;
if (offset == length - 1) {
offset = 0;
nrap++;
}
else {
offset++;
}
}
else {
if (pattern) {
if (offset >= 1) {
offset = auxArray[offset - 1];
}
else offset = 0;
pattern = false;
i--;
}
}
}
g << nrap << "\n";
}
int main()
{
Read();
CompleteAuxArray();
Substr();
}