Prerequisite 1:    substring test in C++

The find( ) function in the string class returns the position of a substring: 

#include <iostream>

using namespace std;

int main()
{
   string string1 = "WWABCDEABAA";
   string string2 = "ABCDE";
   string string3 = "ABCDX";

   cout << string1.find(string2) << endl;  // 2
   cout << string1.find(string3) << endl;  // 4294967295
   cout << string::npos << endl;           // 4294967295

   /* ----------------------------------------------------------------
      How to check is string2 is a substring of string1
      ---------------------------------------------------------------- */
   if ( string1.find(string2) != string::npos )
      cout << string2 << " is in " << string1;
   else
      cout << string2 << " is NOT in " << string1;
}

DEMO: CCC/2020/Progs/findString.cc

Prerequisite 2:    how to rotate a string

  

#include <iostream>

using namespace std;

int main()
{
   string str = "ABCDEFGHIJ";
   string newStr;

   newStr = str.substr(1, str.size()-1);  // Cuts off str[0] ('A')

   cout << newStr << endl;
   cout << str[0] << endl;

   /* ----------------------------------------------------
      Rotate string = cut off str[0] and add it to the end
      ---------------------------------------------------- */
   cout << str.substr(1, str.size()-1) + str[0] << endl;
}

DEMO: CCC/2020/Progs/rotateString.cc

J4 solution    Sketch of solution 

   cin >> text;
   cin >> pattern;

   bool found = false; // Assume pattern is not found in text

   /* ---------------------------------------------------------
      Try every cyclic shift pattern (there is no other way...)

      BTW: this is a brute force search
      --------------------------------------------------------- */
   for ( every possible cyclic shift S of pattern )
   {
      if ( text.find(S) != string::npos )
      {
          found = true;  // Cyclic shift found
          break;
      }


   }

   if ( found )
      cout << "yes" << endl;
   else
      cout << "no" << endl;

Note:   # cyclic shifts = length of pattern   (ABCDE, BCDEA, CDEAB, DEABC, EABCD)

J4 solution    C++ solution 

   cin >> text;
   cin >> pattern;

   bool found = false; // Assume pattern is not found in text

   /* ---------------------------------------------------------
      Try every cyclic shift pattern (there is no other way...)

      BTW: this is a brute force search
      --------------------------------------------------------- */
   for ( int x = 0; x < pattern.size(); x++ )
   {
      if ( text.find(pattern) != string::npos )
      {
          found = true;  // Cyclic shift found
          break;
      }

      pattern = pattern.substr(1, pattern.size()-1);
   }

   if ( found )
      cout << "yes" << endl;
   else
      cout << "no" << endl;

There is no way to reduce the search space - runtime = pattern.length2 × text.length