Interviewfrage: Überprüfen Sie, ob eine Zeichenfolge eine Drehung einer anderen Zeichenfolge ist [geschlossen]

Einem Freund von mir wurde heute beim Interview die folgende Frage für die Position des Softwareentwicklers gestellt:

Bei zwei Zeichenfolgen s1und s2wie werden Sie überprüfen, ob s1es sich um eine gedrehte Version von handelt s2?

Beispiel:

Wenn s1 = "stackoverflow"dann sind die folgenden einige seiner gedrehten Versionen:

"tackoverflows"
"ackoverflowst"
"overflowstack"

wo wie "stackoverflwo"ist keine gedrehte Version.

Die Antwort, die er gab, war:

Nehmen Sie s2und finden Sie das längste Präfix, das eine Unterzeichenfolge von s1ist, die Ihnen den Drehpunkt gibt. Wenn Sie diesen Punkt gefunden haben, brechen Sie s2an diesem Punkt ab, um zu erhalten, s2aund s2büberprüfen Sie dann einfach, obconcatenate(s2a,s2b) == s1

Es sieht nach einer guten Lösung für mich und meinen Freund aus. Aber der Interviewer dachte anders. Er bat um eine einfachere Lösung. Bitte helfen Sie mir, indem Sie mir sagen, wie Sie das machen würden Java/C/C++.

Danke im Voraus.

Zunächst stellen Sie sicher , s1und s2sind von gleicher Länge. Überprüfen Sie dann, ob s2ein Teilstring s1verkettet ist mit s1:

algorithm checkRotation(string s1, string s2) 
  if( len(s1) != len(s2))
    return false
  if( substring(s2,concat(s1,s1))
    return true
  return false
end

In Java:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && ((s1+s1).indexOf(s2) != -1);
}

Eine bessere Antwort wäre sicherlich: "Nun, ich würde die Stackoverflow-Community fragen und wahrscheinlich innerhalb von 5 Minuten mindestens 4 wirklich gute Antworten haben." Gehirne sind gut und alle, aber ich würde einen höheren Wert auf jemanden legen, der weiß, wie man mit anderen zusammenarbeitet, um eine Lösung zu finden.

Ein weiteres Python-Beispiel (basierend auf DER Antwort):

def isrotation(s1,s2):
     return len(s1)==len(s2) and s1 in 2*s2

Da andere eine quadratische Worst-Case-Zeitkomplexitätslösung eingereicht haben, würde ich eine lineare hinzufügen (basierend auf dem KMP-Algorithmus ):

bool is_rotation(const string& str1, const string& str2)
{
  if(str1.size()!=str2.size())
    return false;

  vector<size_t> prefixes(str1.size(), 0);
  for(size_t i=1, j=0; i<str1.size(); i++) {
    while(j>0 && str1[i]!=str1[j])
      j=prefixes[j-1];
    if(str1[i]==str1[j]) j++;
    prefixes[i]=j;
  }

  size_t i=0, j=0;
  for(; i<str2.size(); i++) {
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }
  for(i=0; i<str2.size(); i++) {
    if(j>=str1.size()) return true;
    while(j>0 && str2[i]!=str1[j])
      j=prefixes[j-1];
    if(str2[i]==str1[j]) j++;
  }

  return false;
}

Arbeitsbeispiel

EDIT: Die akzeptierte Antwort ist deutlich eleganter und effizienter als diese, wenn Sie sie erkennen. Ich habe diese Antwort als das belassen, was ich tun würde, wenn ich nicht daran gedacht hätte, die ursprüngliche Saite zu verdoppeln.

Ich würde es nur brutal erzwingen. Überprüfen Sie zuerst die Länge und versuchen Sie dann jeden möglichen Rotationsversatz. Wenn keiner von ihnen funktioniert, geben Sie false zurück. Wenn einer von ihnen dies tut, geben Sie sofort true zurück.

Es besteht keine besondere Notwendigkeit zu verketten - verwenden Sie einfach Zeiger (C) oder Indizes (Java) und gehen Sie beide entlang, einen in jeder Zeichenfolge - beginnend am Anfang einer Zeichenfolge und dem aktuellen Rotationsversatz der Kandidaten in der zweiten Zeichenfolge und bei Bedarf umbrechen . Überprüfen Sie die Zeichengleichheit an jedem Punkt in der Zeichenfolge. Wenn Sie am Ende der ersten Zeichenfolge angelangt sind, sind Sie fertig.

Es wäre wahrscheinlich genauso einfach zu verketten - obwohl es wahrscheinlich weniger effizient ist, zumindest in Java.

Hier ist eine, die Regex nur zum Spaß verwendet:

boolean isRotation(String s1, String s2) {
   return (s1.length() == s2.length()) && (s1 + s2).matches("(.*)(.*)\\2\\1");
}

Sie können es etwas einfacher machen, wenn Sie ein spezielles Trennzeichen verwenden, das garantiert nicht in einer der beiden Zeichenfolgen enthalten ist.

boolean isRotation(String s1, String s2) {
   // neither string can contain "="
   return (s1 + "=" + s2).matches("(.*)(.*)=\\2\\1");
}

Sie können stattdessen auch Lookbehind mit endlicher Wiederholung verwenden:

boolean isRotation(String s1, String s2) {
   return (s1 + s2).matches(
      String.format("(.*)(.*)(?<=^.{%d})\\2\\1", s1.length())
   );
}

Whoa, whoa ... warum sind alle so begeistert von einer O(n^2)Antwort? Ich bin mir sicher, dass wir es hier besser machen können. Die obige Antwort enthält eine O(n)Operation in einer O(n)Schleife (den Aufruf von substring / indexOf). Auch mit einem effizienteren Suchalgorithmus; sagen Boyer-Mooreoder KMP, der schlimmste Fall ist immer noch O(n^2)mit Duplikaten.

Eine O(n)zufällige Antwort ist einfach; Nehmen Sie einen Hash (wie einen Rabin-Fingerabdruck), der ein O(1)Schiebefenster unterstützt . Hash-String 1, dann Hash-String 2, und verschieben Sie das Fenster für Hash 1 um den String und prüfen Sie, ob die Hash-Funktionen kollidieren.

Wenn wir uns vorstellen, dass der schlimmste Fall so etwas wie "Scannen von zwei DNA-Strängen" ist, steigt die Wahrscheinlichkeit von Kollisionen, und dies degeneriert wahrscheinlich zu so etwas O(n^(1+e))oder so (hier nur erraten).

Schließlich gibt es eine deterministische O(nlogn)Lösung, die außen eine sehr große Konstante hat. Grundsätzlich besteht die Idee darin, eine Faltung der beiden Saiten vorzunehmen. Der Maximalwert der Faltung ist die Rotationsdifferenz (wenn sie gedreht werden); ein O(n)Scheck bestätigt. Das Schöne ist, dass wenn es zwei gleiche Maximalwerte gibt, beide auch gültige Lösungen sind. Sie können die Faltung mit zwei FFTs und einem Punktprodukt sowie einer iFFT durchführen nlogn + nlogn + n + nlogn + n == O(nlogn).

Da Sie nicht mit Nullen auffüllen können und nicht garantieren können, dass die Zeichenfolgen 2 ^ n lang sind, sind die FFTs nicht die schnellen. Sie werden die langsamen sein, O(nlogn)aber immer noch eine viel größere Konstante als der CT-Algorithmus.

Alles in allem bin ich absolut zu 100% sicher, dass es hier eine deterministische O(n)Lösung gibt, aber verdammt, wenn ich sie finden kann.

Stellen Sie zunächst sicher, dass die beiden Saiten die gleiche Länge haben. In C können Sie dies dann mit einer einfachen Zeigeriteration tun.

int is_rotation(char* s1, char* s2)
{
  char *tmp1;
  char *tmp2;
  char *ref2;

  assert(s1 && s2);
  if ((s1 == s2) || (strcmp(s1, s2) == 0))
    return (1);
  if (strlen(s1) != strlen(s2))
    return (0);

  while (*s2)
    {
      tmp1 = s1;
      if ((ref2 = strchr(s2, *s1)) == NULL)
        return (0);
      tmp2 = ref2;
      while (*tmp1 && (*tmp1 == *tmp2))
        {
          ++tmp1;
          ++tmp2;
          if (*tmp2 == '\0')
            tmp2 = s2;
        }
      if (*tmp1 == '\0')
        return (1);
      else
        ++s2;
    }
  return (0);
}

Hier ist ein O(n)und an Ort und Stelle Alghoritmus. Es verwendet den <Operator für die Elemente der Zeichenfolgen. Es ist natürlich nicht meins. Ich habe es von hier genommen (Die Seite ist in polnischer Sprache. Ich bin in der Vergangenheit einmal darauf gestoßen und konnte so etwas jetzt nicht auf Englisch finden, also zeige ich, was ich habe :)).

bool equiv_cyc(const string &u, const string &v)
{
    int n = u.length(), i = -1, j = -1, k;
    if (n != v.length()) return false;

    while( i<n-1 && j<n-1 )
    {
        k = 1;
        while(k<=n && u[(i+k)%n]==v[(j+k)%n]) k++;
        if (k>n) return true;
        if (u[(i+k)%n] > v[(j+k)%n]) i += k; else j += k;
    }
    return false;
}

Ich denke, es ist besser, dies zu tun in Java:

boolean isRotation(String s1,String s2) {
    return (s1.length() == s2.length()) && (s1+s1).contains(s2);
}

In Perl würde ich tun:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && ($string1.$string1)=~/$string2/;
}

oder noch besser mit der Indexfunktion anstelle des regulären Ausdrucks:

sub isRotation {
 my($string1,$string2) = @_;
 return length($string1) == length($string2) && index($string2,$string1.$string1) != -1;
}

Ich bin mir nicht sicher, ob dies die effizienteste Methode ist, aber es könnte relativ interessant sein : die Burrows-Wheeler-Transformation . Gemäß dem WP-Artikel ergeben alle Umdrehungen des Eingangs den gleichen Ausgang. Für Anwendungen wie die Komprimierung ist dies nicht wünschenswert, daher wird die ursprüngliche Drehung angezeigt (z. B. durch einen Index; siehe Artikel). Für einen einfachen rotationsunabhängigen Vergleich klingt dies jedoch ideal. Natürlich ist es nicht unbedingt ideal effizient!

Nehmen Sie jedes Zeichen als Amplitude und führen Sie eine diskrete Fourier-Transformation durch. Wenn sie sich nur durch Drehung unterscheiden, sind die Frequenzspektren innerhalb des Rundungsfehlers gleich. Dies ist natürlich ineffizient, es sei denn, die Länge ist eine Potenz von 2, so dass Sie eine FFT durchführen können :-)

Bisher hat noch niemand einen Modulo-Ansatz angeboten. Hier ist einer:

static void Main(string[] args)
{
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "ztackoverflow"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "ackoverflowst"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "overflowstack"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "stackoverflwo"));
    Console.WriteLine("Rotation : {0}",
        IsRotation("stackoverflow", "tackoverflwos"));
    Console.ReadLine();
}

public static bool IsRotation(string a, string b)
{
    Console.WriteLine("\nA: {0} B: {1}", a, b);

    if (b.Length != a.Length)
        return false;

    int ndx = a.IndexOf(b[0]);
    bool isRotation = true;
    Console.WriteLine("Ndx: {0}", ndx);
    if (ndx == -1) return false;
    for (int i = 0; i < b.Length; ++i)
    {
        int rotatedNdx = (i + ndx) % b.Length;
        char rotatedA = a[rotatedNdx];

        Console.WriteLine( "B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA );

        if (b[i] != rotatedA)
        {
            isRotation = false;
            // break; uncomment this when you remove the Console.WriteLine
        }
    }
    return isRotation;
}

Ausgabe:

A: stackoverflow B: ztackoverflow
Ndx: -1
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
B: o A[12]: w
B: s A[0]: s
Rotation : False

[EDIT: 2010-04-12]

piotr bemerkte den Fehler in meinem Code oben. Es tritt ein Fehler auf, wenn das erste Zeichen in der Zeichenfolge zweimal oder öfter vorkommt. Zum Beispiel ergab ein stackoverflowTest gegen owstackoverflowfalse, wenn es wahr sein sollte.

Vielen Dank an piotr für das Erkennen des Fehlers.

Hier ist der korrigierte Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace TestRotate
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ztackoverflow"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ackoverflowst"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "stackoverflwo"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "tackoverflwos"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "owstackoverfl"));

            Console.ReadLine();
        }

        public static bool IsRotation(string a, string b)
        {
            Console.WriteLine("\nA: {0} B: {1}", a, b);

            if (b.Length != a.Length)
                return false;

            if (a.IndexOf(b[0]) == -1 )
                return false;

            foreach (int ndx in IndexList(a, b[0]))
            {
                bool isRotation = true;

                Console.WriteLine("Ndx: {0}", ndx);

                for (int i = 0; i < b.Length; ++i)
                {
                    int rotatedNdx = (i + ndx) % b.Length;
                    char rotatedA = a[rotatedNdx];

                    Console.WriteLine("B: {0} A[{1}]: {2}", b[i], rotatedNdx, rotatedA);

                    if (b[i] != rotatedA)
                    {
                        isRotation = false;
                        break;
                    }
                }
                if (isRotation)
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program
}//namespace TestRotate

Hier ist die Ausgabe:

A: stackoverflow B: ztackoverflow
Rotation : False

A: stackoverflow B: ackoverflowst
Ndx: 2
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
Rotation : True

A: stackoverflow B: overflowstack
Ndx: 5
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
Rotation : True

A: stackoverflow B: stackoverflwo
Ndx: 0
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: tackoverflwos
Ndx: 1
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
B: w A[11]: o
Rotation : False

A: stackoverflow B: owstackoverfl
Ndx: 5
B: o A[5]: o
B: w A[6]: v
Ndx: 11
B: o A[11]: o
B: w A[12]: w
B: s A[0]: s
B: t A[1]: t
B: a A[2]: a
B: c A[3]: c
B: k A[4]: k
B: o A[5]: o
B: v A[6]: v
B: e A[7]: e
B: r A[8]: r
B: f A[9]: f
B: l A[10]: l
Rotation : True

Hier ist der Lambda-Ansatz:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace IsRotation
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ztackoverflow"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "ackoverflowst"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "overflowstack"));
            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "stackoverflwo"));

            Console.WriteLine("Rotation : {0}",
                IsRotation("stackoverflow", "owstackoverfl"));

            string strToTestFrom = "stackoverflow";
            foreach(string s in StringRotations(strToTestFrom))
            {
                Console.WriteLine("is {0} rotation of {1} ? {2}",
                    s, strToTestFrom,
                    IsRotation(strToTestFrom, s) );
            }
            Console.ReadLine();
        }

        public static IEnumerable<string> StringRotations(string src)
        {
            for (int i = 0; i < src.Length; ++i)
            {
                var sb = new StringBuilder();
                for (int x = 0; x < src.Length; ++x)
                    sb.Append(src[(i + x) % src.Length]);

                yield return sb.ToString();
            }
        }

        public static bool IsRotation(string a, string b)
        {
            if (b.Length != a.Length || a.IndexOf(b[0]) < 0 ) return false;
            foreach(int ndx in IndexList(a, b[0]))
            {
                int i = ndx;
                if (b.ToCharArray().All(x => x == a[i++ % a.Length]))
                    return true;
            }
            return false;
        }

        public static IEnumerable<int> IndexList(string src, char c)
        {
            for (int i = 0; i < src.Length; ++i)
                if (src[i] == c)
                    yield return i;
        }

    }//class Program

}//namespace IsRotation

Hier ist die Ausgabe des Lambda-Ansatzes:

Rotation : False
Rotation : True
Rotation : True
Rotation : False
Rotation : True
is stackoverflow rotation of stackoverflow ? True
is tackoverflows rotation of stackoverflow ? True
is ackoverflowst rotation of stackoverflow ? True
is ckoverflowsta rotation of stackoverflow ? True
is koverflowstac rotation of stackoverflow ? True
is overflowstack rotation of stackoverflow ? True
is verflowstacko rotation of stackoverflow ? True
is erflowstackov rotation of stackoverflow ? True
is rflowstackove rotation of stackoverflow ? True
is flowstackover rotation of stackoverflow ? True
is lowstackoverf rotation of stackoverflow ? True
is owstackoverfl rotation of stackoverflow ? True
is wstackoverflo rotation of stackoverflow ? True

Da hat niemand eine C ++ Lösung gegeben. hier ist es es:

bool isRotation(string s1,string s2) {

  string temp = s1;
  temp += s1;
  return (s1.length() == s2.length()) && (temp.find(s2) != string::npos);
}

Der einfache Zeigerrotationstrick von Opera funktioniert, ist jedoch im schlimmsten Fall zur Laufzeit äußerst ineffizient. Stellen Sie sich einfach eine Zeichenfolge mit vielen langen, sich wiederholenden Zeichenfolgen vor, dh:

S1 = HELLOHELLOHELLO1HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

Die "Schleife, bis eine Nichtübereinstimmung vorliegt, dann um eins erhöht und erneut versucht" ist rechnerisch ein schrecklicher Ansatz.

Um zu beweisen, dass Sie den Verkettungsansatz in einfachem C ohne großen Aufwand ausführen können, ist hier meine Lösung:

  int isRotation(const char* s1, const char* s2) {
        assert(s1 && s2);

        size_t s1Len = strlen(s1);

        if (s1Len != strlen(s2)) return 0;

        char s1SelfConcat[ 2 * s1Len + 1 ];

        sprintf(s1SelfConcat, "%s%s", s1, s1);   

        return (strstr(s1SelfConcat, s2) ? 1 : 0);
}

Dies ist in der Laufzeit linear, auf Kosten der O (n) -Speicherauslastung im Overhead.

(Beachten Sie, dass die Implementierung von strstr () plattformspezifisch ist, aber wenn sie besonders hirntot ist, kann sie immer durch eine schnellere Alternative wie den Boyer-Moore-Algorithmus ersetzt werden.)

C #:

s1 == null && s2 == null || s1.Length == s2.Length && (s1 + s1).Contains(s2)

Ich mag DIE Antwort, die prüft, ob s2 eine mit s1 verkettete Teilzeichenfolge von s1 ist.

Ich wollte eine Optimierung hinzufügen, die ihre Eleganz nicht verliert.

Anstatt die Zeichenfolgen zu verketten, können Sie eine Verknüpfungsansicht verwenden (ich kenne keine andere Sprache, aber für C ++ Boost.Range bieten Sie solche Ansichten an).

Da die Überprüfung, ob ein String ein Teilstring eines anderen ist, eine lineare durchschnittliche Komplexität aufweist (die Komplexität im schlimmsten Fall ist quadratisch), sollte diese Optimierung die Geschwindigkeit im Durchschnitt um den Faktor 2 verbessern.

Eine reine Java-Antwort (ohne Null-Checks)

private boolean isRotation(String s1,String s2){
    if(s1.length() != s2.length()) return false;
    for(int i=0; i < s1.length()-1; i++){
        s1 = new StringBuilder(s1.substring(1)).append(s1.charAt(0)).toString();
        //--or-- s1 = s1.substring(1) + s1.charAt(0)
        if(s1.equals(s2)) return true;
    }
    return false;
}

Und jetzt etwas ganz anderes.

Wenn Sie eine wirklich schnelle Antwort in einem eingeschränkten Kontext wünschen, wenn sich die Zeichenfolgen nicht gegenseitig drehen

• Berechnen Sie eine zeichenbasierte Prüfsumme (wie das Xoring aller Zeichen) für beide Zeichenfolgen. Wenn Signaturen unterschiedlich sind, sind Zeichenfolgen keine Rotationen voneinander.

Einverstanden, es kann fehlschlagen, aber es ist sehr schnell zu sagen, ob Zeichenfolgen nicht übereinstimmen, und wenn sie übereinstimmen, können Sie immer noch einen anderen Algorithmus wie die Verkettung von Zeichenfolgen verwenden, um dies zu überprüfen.

Eine weitere Ruby-Lösung basierend auf der Antwort:

def rotation?(a, b); a.size == b.size and (b*2)[a]; end

Es ist sehr einfach in der Verwendung von PHP zu schreiben strlenund strposFunktionen:

function isRotation($string1, $string2) {
    return strlen($string1) == strlen($string2) && (($string1.$string1).strpos($string2) != -1);
}

Ich weiß nicht, was strposintern verwendet wird, aber wenn es KMP verwendet, ist dies zeitlich linear.

Kehren Sie eine der Saiten um. Nehmen Sie die FFT von beiden (behandeln Sie sie als einfache Folgen von ganzen Zahlen). Multiplizieren Sie die Ergebnisse punktuell. Mit inverser FFT zurücktransformieren. Das Ergebnis hat einen einzelnen Peak, wenn die Saiten Rotationen voneinander sind. Die Position des Peaks gibt an, um wie viel sie relativ zueinander gedreht sind.

Warum nicht so etwas?

//is q a rotation of p?
bool isRotation(string p, string q) {
    string table = q + q;    
    return table.IndexOf(p) != -1;
}

Natürlich können Sie auch Ihre eigene IndexOf () -Funktion schreiben. Ich bin mir nicht sicher, ob .NET einen naiven oder einen schnelleren Weg verwendet.

Naiv:

int IndexOf(string s) {
    for (int i = 0; i < this.Length - s.Length; i++)
        if (this.Substring(i, s.Length) == s) return i;
    return -1;
}

Schneller:

int IndexOf(string s) {
    int count = 0;
    for (int i = 0; i < this.Length; i++) {
        if (this[i] == s[count])
            count++;
        else
            count = 0;
        if (count == s.Length)
            return i - s.Length;
    }
    return -1;
}

Bearbeiten: Ich könnte einige Probleme haben; Ich habe keine Lust zu überprüfen. ;)

Ich würde das in Perl machen :

sub isRotation { 
     return length $_[0] == length $_[1] and index($_[1],$_[0],$_[0]) != -1; 
}

int rotation(char *s1,char *s2)
{
    int i,j,k,p=0,n;
    n=strlen(s1);
    k=strlen(s2);
    if (n!=k)
        return 0;
    for (i=0;i<n;i++)
    {
        if (s1[0]==s2[i])
        {
            for (j=i,k=0;k<n;k++,j++)
            {
                if (s1[k]==s2[j])
                    p++;
                if (j==n-1)
                    j=0;
            }
        }
    }
    if (n==p+1)
      return 1;
    else
      return 0;
}

Verbinden Sie sich string1mit string2und verwenden Sie den KMP-Algorithmus , um zu überprüfen, ob string2eine neu gebildete Zeichenfolge vorhanden ist. Weil die zeitliche Komplexität von KMP geringer ist als substr.