Überprüft, ob Links- und Rechtsverschiebungen einer beliebigen Zeichenfolge zur angegebenen Zeichenfolge führen

Eine Sammlung von Zeichen wird durch den String-Datentyp dargestellt. Zur logischen Anordnung werden Buchstaben, Zahlen, Symbole und Leerzeichen verwendet. Die meisten Computersprachen verwenden einfache oder doppelte Anführungszeichen, um Zeichenfolgen einzuschließen und sie von anderen Datentypen zu unterscheiden.

Programmierer verwenden häufig Zeichenfolgen, um einige Eingabe- und Ausgabevorgänge durchzuführen, Textdaten zu speichern und zu bearbeiten usw. Zu den gängigen Vorgängen für Zeichenfolgen gehören die Verkettung (Zusammenführen von zwei oder mehr Zeichenfolgen), das Extrahieren von Teilzeichenfolgen (Abrufen eines Teils einer Zeichenfolge) und die Suche nach bestimmten Zeichen oder Mustern in einer Zeichenfolge.

Methode

Wir können die folgende Methode verwenden, um zu bestimmen, ob die Ergebnisse der Links- und Rechtsverschiebung einer Zeichenfolge für jede Zeichenfolge −

sind

Methode 1. Brute-Force-Cracking-Methode −

Methode 2. Teilzeichenfolge prüfen −

Methode 1: Brute-Force-Cracking-Methode

Generieren Sie mithilfe der Brute-Force-Methode alle Links- und Rechtsverschiebungen der Eingabezeichenfolge und vergleichen Sie jede Zeichenfolge mit der Zielzeichenfolge. Die zeitliche Komplexität dieser Methode, wobei n die Länge der Zeichenfolge ist, beträgt O(n2).

Grammatik

Durchlaufen Sie alle möglichen Links- und Rechtsverschiebungen der ursprünglichen Zeichenfolge und vergleichen Sie sie mit der angegebenen Zeichenfolge. Dies ist eine Brute-Force-Methode, um festzustellen, ob eine Links- und Rechtsverschiebung einer Zeichenfolge zur angegebenen Zeichenfolge führt. Die allgemeine Syntax dieser Strategie lautet wie folgt: −

string_shift_check (original_string, given_string):
   n = length of original string
   for int i from 0 to n-1:
      left shift = original string[i:n] + original string[0:i]
      right shift = original string[n-i:n] + original string[0:n-i]
      if left shift == given string or right shift == given string:
         return True
   return False

Algorithmus

Die Brute-Force-Methode, um festzustellen, ob eine Links- oder Rechtsverschiebung einer Zeichenfolge zu einer bestimmten Zeichenfolge führt, besteht darin, jede mögliche Verschiebung der Zeichenfolge zu testen und festzustellen, ob eine davon zur angegebenen Zeichenfolge passt. Der Algorithmus lautet wie folgt: −

Schritt 1 − Beginnen Sie mit der Initialisierung einer Variablen auf 0, die die aktuelle Schichtanzahl darstellt.

Schritt 2 – Wenn die Schichtzahl kleiner als die Stringlänge ist –

• Verschieben Sie die Zeichenfolge nach links und verschieben Sie das erste Zeichen an das Ende der Zeichenfolge.

• Stellen Sie sicher, dass die verschobene Zeichenfolge mit der bereitgestellten Zeichenfolge übereinstimmt. Bei Übereinstimmung wird die wahre Antwort gegeben.

• Verschieben Sie eine Zeichenfolge nach rechts, indem Sie das letzte Zeichen an den Anfang verschieben.

• Stellen Sie sicher, dass die verschobene Zeichenfolge mit der bereitgestellten Zeichenfolge übereinstimmt. Wenn es eine Übereinstimmung gibt, geben Sie die richtige Antwort an.

• Schichtzahl um 1 erhöhen.

Schritt 3 – Wenn nach dem Ausprobieren aller möglichen Verschiebungen keine Übereinstimmung gefunden wird, geben Sie „false“ zurück.

Die chinesische Übersetzung von

Beispiel 1

lautet:

Beispiel 1

Diese Implementierung zeigt, dass die Funktion „Shifted String“ zwei String-Parameter s und target empfängt und ein boolesches Ergebnis zurückgibt, das angibt, ob das Ziel eine Links- oder Rechtsverschiebung von s ist.

Bevor festgestellt wird, ob das Ziel eine verschobene Version von s ist, überprüft die Funktion zunächst, ob die Längen der beiden Zeichenfolgen gleich sind. Danach wird ein neuer String erstellt, indem die Teilstrings vor und nach jeder möglichen Verschiebungsposition kombiniert werden. Diese Methode gibt true zurück, wenn die nach links oder rechts verschobenen Zeichenfolgen in der gewünschten Zeichenfolge ähnlich sind. Ist dies nicht der Fall, geben Sie false zurück.

In der Hauptfunktion definieren wir zwei Beispielzeichenfolgen s und target und verwenden diese Zeichenfolgen, um die Shifted String-Methode aufzurufen. Das Programm gibt dann an, ob target die verschobene Form von s ist.

#include <iostream>
#include <string>

using namespace std;

bool isShiftedString(string s, string target) {
   if(s.length() != target.length()) {
      return false;
   }
   int n = s.length();
   for(int i = 0; i < n; i++) {
      string leftShift = s.substr(i) + s.substr(0, i); // left shift the string
      string rightShift = s.substr(n-i) + s.substr(0, n-i); // right shift the string
      if(leftShift == target || rightShift == target) {
         return true;
      }
   }
   return false;
}

int main() {
   string s = "abcde";
   string target = "cdeab";
   if(isShiftedString(s, target)) {
      cout << "The string is shifted." << endl;
   } else {
      cout << "The string is not shifted." << endl;
   }
   return 0;
}

Ausgabe

The string is shifted.

Methode 2: Teilzeichenfolge prüfen

Um festzustellen, ob eine kleinere Zeichenfolge Teil einer längeren Zeichenfolge ist, können Sie die Methode „Teilzeichenfolge prüfen“ verwenden. Bei diesem Prozess werden einzelne Teilzeichenfolgen mit der gleichen Länge wie die kleinere Zeichenfolge mit der kleineren Zeichenfolge selbst verglichen, während über die längere Zeichenfolge iteriert wird. Wenn zwei Zeichenfolgen übereinstimmen, bestätigt dies, dass die kürzere Zeichenfolge tatsächlich eine Teilmenge des größeren Texts ist. Um dem Aufsatz mehr Komplexität und Abwechslung in der Satzlänge zu verleihen, sollte die Idee in einfache, aber ansprechende Teile zerlegt werden.

Grammatik

Die folgende Syntax kann verwendet werden, um zu bestimmen, ob Links- und Rechtsverschiebungen einer beliebigen Zeichenfolge zur angegebenen Zeichenfolge führen -

if (string_to_check_in.find(substring_to_check) != -1):
   //Substring found in string, so it is a left or right shift
else:
   //Substring not found, so it is not a left or right shift

Algorithmus

Der folgende Algorithmus wird verwendet, um zu bestimmen, ob Links- und Rechtsverschiebungen einer Zeichenfolge die bereitgestellte Zeichenfolge erzeugen –

Schritt 1 – Beginnen Sie mit der Eingabe der Eingabezeichenfolge und der Zielzeichenfolge.

Schritt 2 – Stellen Sie sicher, dass die Länge der Eingabezeichenfolge und die Länge der Zielzeichenfolge gleich sind. Wenn nicht gleich, wird False zurückgegeben.

Schritt 3 − Um eine neue Sequenz zu erstellen, muss die Eingabezeichenfolge mit der Ausgabezeichenfolge zusammengeführt werden.

Schritt 4 – Ein Vergleich ist erforderlich, um zu bestätigen, ob die Eingabezeichenfolge in der neu erstellten Sequenz enthalten ist.

Schritt 5 – Wenn die beiden Zeichenfolgen genau gleich sind, ist die Antwort unbestreitbar; andernfalls lautet die Antwort „Nein“.

Die chinesische Übersetzung von

Beispiel 2

lautet:

Beispiel 2

Dies ist ein C++-Code, der bestimmt, ob das Verschieben einer Zeichenfolge nach links und rechts eine bestimmte Zeichenfolge erzeugt -

此示例研究了两个数组s1和s2之间的连接，以观察它们是否共享任何相似的字符串。通过坚持s1和s2的长度需要相同的前提，它们被合并为一个名为"s1s1"的数组。进一步对该数组进行分析，以确定是否可以找到s2的一部分，搜索的结果将输出"true"或"false"。这种技术提供了对关联的基本反应，用于进一步评估s1和s2的左右字段，以确认两个数组之间的关联。

#include <iostream>
#include <string>

using namespace std;

bool checkForSubstring(string s1, string s2) {
   if (s1.length() != s2.length()) {
      return false;
   }
    
   string s1s1 = s1 + s1;
    
   if (s1s1.find(s2) != string::npos) {
      return true;
   }
    
   return false;
}
int main() {
   string s1 = "abcd";
   string s2 = "cdab";
    
   if (checkForSubstring(s1, s2)) {
      cout << "Yes, left or right shift of string " << s1 << " results in " << s2 << endl;
   } else {
      cout << "No, left or right shift of string " << s1 << " does not result in " << s2 << endl;
   }
   return 0;
}

输出

Yes, left or right shift of string abcd results in cdab

结论

我们得到了一个字符串用于这个主题，我们需要确定这个字符串是否可以通过反复应用左移和右移来生成。

将提供的字符串与自身连接起来，并确定新字符串是否保留了原始字符串，这样可以解决这个问题。如果是的话，对字符串本身执行左移和右移操作将得到原始字符串。

作为一种替代方案，我们可以遍历每个移位位置，看看是否有任何移位后的字符串与输入字符串匹配。

解决方案的时间复杂度在这两种情况下都是O(n2)，其中n是字符串的长度。ft和任何字符串的右移都会导致给定的字符串−

Das obige ist der detaillierte Inhalt vonÜberprüft, ob Links- und Rechtsverschiebungen einer beliebigen Zeichenfolge zur angegebenen Zeichenfolge führen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!