0

Есть программа, которая в цикле сравнивает строки, всё в ней работает, но в итоге превышается тайм лимит на 0,001 - 0,007 секунды. Решил с каждой итерацией отсекать первый символ, для ускорения работы цикла, но как это сделать?! P.S. Длина строки может достигать 100,000 символов.

Код:

#include <fstream>
#include <cstring>
std::ofstream cout("output.txt");
std::ifstream cin("input.txt");

int main() {
   char e[100002] , m[100002] , s[100002];
   int l ;
   cin >> e ;
   cin >> m ;
   cin >> s ;
   l = strlen(e);
   for (int i=0; i <= l ;i++) {
   if (strncmp(m,e,i) != 0 || strncmp(s,e,i) != 0 ) {
        if (strncmp(m,e,i) == 0 && strncmp(s,e,i) != 0 ) { cout << "Masha";
            break; }
        if (strncmp(m,e,i) != 0 && strncmp(s,e,i) == 0 ) { cout << "Sasha";
            break; }
        if (strncmp(m,e,i) != 0 && strncmp(s,e,i) != 0 ) { cout << "Draw";
            break; }
        break;
   }
else { continue;}
}
return 0;
}
6
  • 1. Не провериться равенство 1 символа в строках. 2. Нужно отсекать постоянно, иначе эффекта не будет.
    – Rob Clark
    3 окт 2017 в 17:47
  • Что подразумеваете под отсекать? 3 окт 2017 в 17:53
  • Опишите логику. Нужно найти, у кого строка совпадает и совпадение длиннее? 3 окт 2017 в 17:54
  • Вам нужно преобразовать в compressed radix tree. Тогда всё сведётся к очень быстрому проходу по дереву.
    – 0andriy
    3 окт 2017 в 18:20
  • @0andriy Что это не знаю, но за подсказку спасибо.
    – Rob Clark
    3 окт 2017 в 18:43

2 ответа 2

1

Нужно инкрементировать указатели. m указывает на начало строки, а после m++ уже на второй символ и так далее. и все время сравнивать 1 символ. То есть

for (int i=0; i < l ;i++) {
   if (m[i]!= e[i] || s[i] != e[i] ) {
        if (m[i]== e[i] && s[i] != e[i] ) { cout << "Masha";
            break; }
        if (m[i]!= e[i] && s[i] == e[i]) { cout << "Sasha";
            break; }
        if (m[i]!= e[i] && s[i] != e[i] ) { cout << "Draw";
            break; }
        break;
   }
//else быть не может    

}
1
  • TimeLimit исчез, но теперь решение не всегда верно, иду фиксить, спасибо )
    – Rob Clark
    3 окт 2017 в 18:10
0

Делай сравнение только 1 раз:

for (int i=0; i <= l ;i++) 
{
    int m_e_i = strncmp(m,e,i);
    int s_e_i = strncmp(s,e,i);
    if (m_e_i != 0 || s_e_i !=0 ) 
    {
        if (m_e_i == 0 && s_e_i !=) {}
        ...
        ...
    }
}
3
  • Great idea! Попробую.
    – Rob Clark
    3 окт 2017 в 17:49
  • Не помогло, снизило на 0,001 в пике (
    – Rob Clark
    3 окт 2017 в 17:56
  • Это правильно было, но у него постоянно проверяются строки, которые уже проверено, что равны. 3 окт 2017 в 17:58

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.