Pytanie do wywiadu: Sprawdź, czy jeden ciąg znaków jest rotacją drugiego ciągu [zamknięty]

Mój przyjaciel otrzymał dziś podczas wywiadu następujące pytanie na stanowisko programisty:

Biorąc pod uwagę dwa ciągi s1i s2jak sprawdzisz, czy s1jest to obrócona wersja s2?

Przykład:

Jeśli s1 = "stackoverflow"to, oto niektóre z jego obróconych wersji:

"tackoverflows"
"ackoverflowst"
"overflowstack"

gdzie jak "stackoverflwo"to nie obrócony wersja.

Odpowiedź, którą udzielił, brzmiała:

Weź s2i znajdź najdłuższy prefiks, który jest podrzędnym ciągiem s1, który da ci punkt obrotu. Po znalezieniu tego punktu, przerwa s2w tym momencie, aby uzyskać s2aa s2b, a potem po prostu sprawdzić, czyconcatenate(s2a,s2b) == s1

To wygląda na dobre rozwiązanie dla mnie i mojego przyjaciela. Ale ankieter pomyślał inaczej. Poprosił o prostsze rozwiązanie. Pomóż mi, mówiąc, jak byś to zrobił Java/C/C++?

Z góry dziękuję.

Najpierw upewnij się, s1i s2są tej samej długości. Następnie sprawdź, czy s2jest podciąg s1połączony z 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

W Javie:

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

Z pewnością lepszą odpowiedzią byłoby: „Cóż, zapytałbym społeczność stackoverflow i prawdopodobnie uzyskałbym co najmniej 4 naprawdę dobre odpowiedzi w ciągu 5 minut”. Mózgi są dobre, ale większą wartość miałbym dla kogoś, kto wie, jak współpracować z innymi, aby znaleźć rozwiązanie.

Kolejny przykład python (oparty na odpowiedzi):

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

Ponieważ inni przedstawili kwadratowe rozwiązanie problemu złożoności w najgorszym przypadku, dodam liniowe (oparte na algorytmie KMP ):

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;
}

przykład roboczy

EDYCJA: Przyjęta odpowiedź jest wyraźnie bardziej elegancka i wydajniejsza, jeśli ją zauważysz. Pozostawiłem tę odpowiedź jako to, co zrobiłbym, gdybym nie pomyślał o podwojeniu oryginalnej struny.

Po prostu użyłbym tego brutalnie. Najpierw sprawdź długość, a następnie wypróbuj każde możliwe przesunięcie obrotu. Jeśli żaden z nich się nie powiedzie, zwróć false - jeśli którykolwiek z nich się sprawdzi, natychmiast zwróć true.

Nie ma szczególnej potrzeby konkatenacji - wystarczy użyć wskaźników (C) lub indeksów (Java) i przejść obie strony, po jednym w każdym ciągu - zaczynając od początku jednego ciągu i bieżącego przesunięcia obrotu kandydata w drugim ciągu i zawijając w razie potrzeby . Sprawdź równość znaków w każdym punkcie ciągu. Jeśli dojdziesz do końca pierwszego ciągu, gotowe.

Prawdopodobnie byłoby tak łatwo połączyć - choć prawdopodobnie mniej wydajne, przynajmniej w Javie.

Oto jeden z wyrażeń regularnych dla zabawy:

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

Możesz to uprościć, jeśli możesz użyć specjalnego znaku ograniczającego, który nie będzie w żadnym łańcuchu.

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

Zamiast tego możesz także użyć lookbehind ze skończonym powtarzaniem:

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

Zaraz, zaraz ... dlaczego wszyscy są tak podekscytowani O(n^2)odpowiedzią? Jestem przekonany, że możemy tu zrobić lepiej. Powyższa odpowiedź obejmuje O(n)operację w O(n)pętli (wywołanie substring / indexOf). Nawet z bardziej wydajnym algorytmem wyszukiwania; powiedzmy Boyer-Moorelub KMP, najgorszy przypadek wciąż dotyczy O(n^2)duplikatów.

O(n)Randomizowane odpowiedź jest prosta; weź skrót (jak odcisk palca Rabina), który obsługuje O(1)przesuwne okno; hash string 1, następnie hash string 2 i przejdź do przesuwania okna dla hash 1 wokół łańcucha i sprawdź, czy funkcje hash nie kolidują.

Jeśli wyobrażamy sobie, że najgorszym przypadkiem jest coś takiego jak „skanowanie dwóch nici DNA”, to prawdopodobieństwo kolizji rośnie, a to prawdopodobnie przeradza się w coś takiego O(n^(1+e))lub coś (zgaduję tutaj).

Wreszcie istnieje deterministyczne O(nlogn)rozwiązanie, które ma bardzo dużą stałą na zewnątrz. Zasadniczo chodzi o splot dwóch ciągów. Maksymalna wartość splotu będzie różnicą obrotów (jeśli zostaną obrócone); an O(n)potwierdza czek. Zaletą jest to, że jeśli istnieją dwie równe wartości maksymalne, oba są również poprawnymi rozwiązaniami. Możesz dokonać splotu za pomocą dwóch FFT i iloczynu i iFFT, więc nlogn + nlogn + n + nlogn + n == O(nlogn).

Ponieważ nie można uzupełniać zerami i nie można zagwarantować, że ciągi mają długość 2 ^ n, FFT nie będą szybkimi; będą to te powolne, O(nlogn)ale o wiele większa stała niż algorytm CT.

To powiedziawszy, jestem absolutnie w 100% przekonany, że istnieje tu deterministyczne O(n)rozwiązanie, ale cholernie, jeśli go znajdę.

Pięść, upewnij się, że 2 struny mają tę samą długość. Następnie w C możesz to zrobić za pomocą prostej iteracji wskaźnika.

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);
}

Oto O(n)i na miejscu algorytm. Używa <operatora dla elementów ciągów. Oczywiście to nie moje. Wziąłem ją stąd (strona jest po polsku. Natknąłem się na nią kiedyś w przeszłości i teraz nie mogłem znaleźć czegoś takiego po angielsku, więc pokazuję, co mam :)).

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;
}

Myślę, że lepiej to zrobić w Java:

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

W Perlu zrobiłbym:

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

lub jeszcze lepiej przy użyciu funkcji indeksu zamiast wyrażenia regularnego:

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

Nie jestem pewien, czy jest to najbardziej wydajna metoda, ale może być stosunkowo interesująca : transformacja Burrowsa-Wheelera . Zgodnie z artykułem WP wszystkie obroty wejścia dają taką samą moc wyjściową. W zastosowaniach takich jak kompresja nie jest to pożądane, dlatego wskazany jest pierwotny obrót (np. Za pomocą indeksu; zobacz artykuł). Ale dla prostego porównania niezależnego od obrotu brzmi idealnie. Oczywiście niekoniecznie jest to idealna wydajność!

Weź każdą postać jako amplitudę i wykonaj na niej dyskretną transformatę Fouriera. Jeśli różnią się tylko obrotem, widma częstotliwości będą takie same jak w obrębie błędu zaokrąglania. Oczywiście jest to nieefektywne, chyba że długość jest potęgą 2, więc możesz wykonać FFT :-)

Nikt jeszcze nie zaproponował podejścia modulo, więc oto jedno:

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;
}

Wynik:

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

[EDYCJA: 2010-04-12]

piotr zauważył błąd w moim kodzie powyżej. Występuje błąd, gdy pierwszy znak w ciągu występuje dwa razy lub więcej. Na przykład stackoverflowtestowanie z owstackoverflowwynikiem dawało fałsz, kiedy powinno być prawdziwe.

Dzięki piotr za wykrycie błędu.

Oto poprawiony kod:

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

Oto wynik:

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

Oto podejście lambda:

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

Oto dane wyjściowe podejścia lambda:

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

Ponieważ nikt nie podał rozwiązania w języku C ++. tutaj to:

bool isRotation(string s1,string s2) {

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

Prosta sztuczka rotacji wskaźnika w Operze działa, ale jest wyjątkowo nieefektywna w najgorszym przypadku w czasie działania. Po prostu wyobraź sobie ciąg znaków z wieloma długimi powtarzającymi się seriami znaków, tj .:

S1 = HELLOHELLOHELLO1 HELLOHELLOHELLO2

S2 = HELLOHELLOHELLO2HELLOHELLOHELLO1

„Pętla, aż nastąpi niedopasowanie, a następnie zwiększenie o jeden i spróbuj ponownie” jest okropnym podejściem obliczeniowym.

Aby udowodnić, że możesz zastosować metodę konkatenacji na zwykłym C bez większego wysiłku, oto moje rozwiązanie:

  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);
}

Jest to liniowe w czasie wykonywania, kosztem wykorzystania pamięci O (n) w kosztach ogólnych.

(Zauważ, że implementacja strstr () jest specyficzna dla platformy, ale jeśli jest szczególnie martwa w mózgu, zawsze można ją zastąpić szybszą alternatywą, taką jak algorytm Boyer-Moore)

DO#:

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

Podoba mi się odpowiedź, która sprawdza, czy s2 jest podciągiem s1 połączonym z s1.

Chciałem dodać optymalizację, która nie traci elegancji.

Zamiast łączyć łańcuchy możesz użyć widoku złączenia (nie znam innego języka, ale dla C ++ Boost.Range zapewnia takie widoki).

Ponieważ sprawdzenie, czy łańcuch jest podciągiem innego, ma złożoność średnią liniową (złożoność najgorszego przypadku jest kwadratowa), ta optymalizacja powinna poprawić szybkość średnio o współczynnik 2.

Czysta odpowiedź Java (bez sprawdzania wartości zerowej)

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;
}

A teraz coś z zupełnie innej beczki.

Jeśli chcesz naprawdę szybkiej odpowiedzi w ograniczonym kontekście, gdy łańcuchy nie obracają się względem siebie

• obliczyć pewną sumę kontrolną opartą na znakach (jak xoring wszystkich znaków) na obu ciągach. Jeżeli podpisy różnią się, ciągi znaków nie są wzajemnie obracane.

Uzgodnione, może się nie powieść, ale bardzo szybko można stwierdzić, czy ciągi się nie zgadzają, a jeśli się zgadzają, nadal można użyć innego algorytmu, takiego jak konkatenacja ciągów.

Innym rozwiązaniem Ruby na podstawie tej odpowiedzi:

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

Pisanie w PHP jest bardzo łatwe przy użyciu strleni strposfunkcji:

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

Nie wiem, co strposużywa wewnętrznie, ale jeśli używa KMP, będzie to liniowe w czasie.

Odwróć jeden z ciągów. Weź FFT obu (traktując je jako proste sekwencje liczb całkowitych). Pomnóż wyniki razem punktowo. Przekształć z powrotem za pomocą odwrotnego FFT. Wynik będzie miał jeden pik, jeśli struny będą się obracać względem siebie - pozycja piku wskaże, o ile są one obrócone względem siebie.

Dlaczego nie coś takiego?

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

Oczywiście możesz napisać własną funkcję IndexOf (); Nie jestem pewien, czy .NET używa naiwnego czy szybszego sposobu.

Naiwny:

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;
}

Szybciej:

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;
}

Edycja: Mogę mieć jakieś problemy off-by-one; nie chcę sprawdzać. ;)

Zrobiłbym to w Perlu :

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;
}

Dołącz string1się string2i używać algorytmu KMP w celu sprawdzenia, czy string2jest obecny w nowo utworzonym ciągiem. Ponieważ złożoność czasowa KMP jest mniejsza niż substr.