There is a program that compares lines in a cycle, everything in it works, but in the end the time limit is exceeded by 0.001 - 0.007 seconds. I decided with each iteration to cut off the first character to speed up the cycle, but how to do it ?! PS The length of the string can be up to 100,000 characters.

Code:

#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; }
  • 1. Do not check the equality of 1 character in rows. 2. It is necessary to cut off constantly, otherwise the effect will not be. - Alexander Ketcher
  • What do you mean by clipping? - HasmikGaryaka
  • Describe the logic. Need to find out who has the same string and longer match? - HasmikGaryaka
  • You need to convert to compressed radix tree. Then everything will be reduced to a very fast passage through the tree. - 0andriy
  • @ 0andriy What I do not know, but thanks for the hint. - Alexander Ketcher

2 answers 2

It is necessary to increment pointers. m indicates the beginning of the line, and after m ++ it is already the second character, and so on. and compare 1 character all the time. I.e

 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 быть не может }
  • TimeLimit has disappeared, but now the solution is not always true, I am fixing, thanks) - Alexander Ketcher

Do the comparison only 1 time:

 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 !=) {} ... ... } }
  • Great idea! I'll try. - Alexander Ketcher
  • It did not help, reduced by 0.001 at the peak ( - Alexander Ketcher
  • It was right, but he constantly checks the lines that have already been verified that they are equal. - HasmikGaryaka