What algorithm to use?

Task:

At Berland State University, the local network between servers does not always work without errors. When transmitting two identical messages in a row, an error may occur, as a result of which the two messages merge into one. With this merger, the end of the first message is combined with the beginning of the second. Of course, the combination can occur only on the same characters. The length of the combination should be a positive number, less than the length of the message text.

For example, when two abrakadabra messages are transmitted in a row, it is possible that it will be transmitted with an error of the described type, and then a message of the form abrakadabrabrakadabra or abrakadabrakadabra will be received (in the first case, the combination occurred on one character ).

Using the received message t, determine whether it is possible that this is the result of the error of the described type of operation of the local network, and if possible, determine the possible value of s.

It should not be considered an error the situation of complete overlap of the friend of the other two messages. For example, if the message “abcd” is received, it should be considered that there is no error in it. Similarly, simply writing one message after another is not a sign of error. For example, if the message “abcabc” is received, it should be considered that there is no error in it.

Input The single line of the output should be a non-empty string t, consisting of lowercase English letters. The length of the string t does not exceed 100 characters.

Output If the message t cannot contain errors, output "NO" (without quotes) into a single line of output.

Otherwise, in the first line print “YES” (without quotes), and in the next line print the string s - a possible message that could lead to an error. If there are several possible answers, it is allowed to display any of them.

Examples:

input data

abrakadabrabrakadabra

output

 YES abrakadabra

input data

 acacacaca

output

 YES acaca

input data

 abcabc

output

 NO

input data

 abababab

output

 YES ababab

input data

 tatbt

output

 NO

Note:

In the second sample, the appropriate response is also the string acacaca.

  • in the examples abcabc and tatbt you do not have the output data just NO - Jiraff537

1 answer 1

  1. We find the length of the string t and its integer division by its midpoint (if the length is odd, we start with the middle character, if it is even, from the one to the left of the middle).
  2. We pass through the line in the opposite direction from the middle character to the second one inclusively (but not to the first one; otherwise, it is just a coincidence of the lines).
  3. Consider a substring from the current character to the end.
  4. If the substring coincides with the beginning of the main line - output YES and substrings and exit, if not - go to the next character. If we have reached the end unsuccessfully, we derive NO .

In C ++ it looks like this:

 #include <vector> #include <string> #include <iostream> #include <iomanip> using namespace std; void test(const string t) { for(size_t l = (t.length()-1)/2, i = l; i > 0; --i) { string s = t.substr(i); if (t.find(s) == 0) { cout << "YES\n" << s << endl; return; } } cout << "NO\n"; } int main() { vector<string> s = { "abrakadabrabrakadabra", "acacacaca", "abcabc", "abababab", "tatbt" }; for(auto t: s) { cout << "---- " << t << endl;; test(t); } }