What's wrong with solving the problem?

Question

C++ / C#

Problem
Vasya recently found out what the cyclic k-extension of the string S is. It can be obtained as follows: glue k instances of the string S, and then take the first k characters of the result.

Having learned this, Vasya was delighted, took a certain string, and began to apply the described operation to it, not remembering which k he took each time.

You are given a part of the string Vasya obtained. Your task is to determine whether Vasya made a mistake in his complex transformations, that is, whether he could get an answer from the original string containing this string as a substring.

Input data
The first line of the input file INPUT.TXT contains the original line, which Vasya carefully wrote down before proceeding with his actions. The second line contains a substring of the result obtained by Vasya. Both strings are not empty and do not exceed 5,000 characters in length. Strings can consist of uppercase and lowercase English letters (case sensitive) as well as numbers.

Output
In the output file OUTPUT.TXT print "NO" if it is possible to say for sure that Vasya made a mistake, and "YES" if he could not have made a mistake.

Examples
1) Input:
abc
abc
Output:
YES
2) Input:
abcd
bcabc
Output:
YES
3) Input:
abcabc
abcA
Output:
NO

Idea
I thought the task was to check if the first and second rows have the same values, but apparently wrong.

#include <iostream>
#include <string>

int main()
{
    std::string str;
    std::string substring;

    std::cin >> str;
    std::cin >> substring;

    bool check = false;

    int i = 0;
    while (!check && i < substring.length())
    {
        if (str.find(substring[i]) == std::string::npos)
        {
            check = true;
        }
        i++;
    }
    if (check)
    {
        std::cout << "NO";
    }
    else
    {
        std::cout << "YES";
    }
}

Answer 1

Your idea is not correct.
You need to draw on a piece of paper and make sure that from the string S you can only get strings of the form S(k1)S(k2)S(k3)...S(kn), Where S(x) is the x-th prefix of the string S, those. first x characters.
In this case, k1 >= k2, ... k1>= kn.
At what all lines of such type can be received.
Proved by induction on the number of operations. Initially, the string is of this kind (k1=string length). After each operation, this string is copied several times and somehow cut off in length. Therefore, any resulting string will be of this form. And each such string can be built: apply operations with k equal to k1, k1+k2, k1+k2+k3... So you will collect all prefixes one by one in n operations.
Now, since you are given a substring of the result in the input file, you need to check that this string consists of the substring S followed by the prefixes of the string S.
So, the example from the condition bcabcconsists of the substring bcand one prefix abc.
There are not very big restrictions in the task, so it is possible to determine for each substring i..j of the resulting string whether it is a suffix of the first string or not. Also, for each substring of the first string, you can determine whether it is a prefix of the second string.
Then you need to build a graph: from position 0, make edges to all positions where some substring of the first line ends at the beginning of the second. From position i>0, make edges to all positions j such that the substring i...j is the prefix of the first string.
Then, if this graph has a path from vertex 0 to the vertex with the number of the length of the second line - YES. Otherwise - NO.
This is a square solution, if the substrings are not searched in a completely stupid way: to check for a suffix, lead the outer loop along the right end, and the inner loop along the left end, descending. This way you can shift the second pointer while the string remains a suffix, checking only one character each time. Similarly, you can check all substrings for a match with a prefix.