Вопрос о Microsoft Интервью: Напишите эффективную программу для сопоставления строк для сопоставления строк?

Question

Напишите эффективную по времени программу C, которая принимает две строки (строка a, строка b) и дает первое вхождение строки b в строке a.

Answer 1

Wikipedia knows all

Answer 2

Многие алгоритм на совпадения строк. Например, алгоритм Кнута-Морриса-Пратт, алгоритм Бойера-Мура. Просто обратитесь к любому руководству по алгоритму.

Answer 3

Напишите эффективную программу на C, которая принимает две строки (строка a, строка b) и дает первое вхождение строки b в строке a.

Он не говорит, что вы делаете повторное согласование с каждой строкой, или любое полезное представление о один является особенно коротким, конкретное содержание, или там быть много времени запуска, то событие запуска, после чего быстро как- возможно сравнение, поэтому: все сложные алгоритмы, упомянутые в других ответах, вероятно, не запрашиваются интервьюером.

Я прочитал «эффективный», чтобы означать, что алгоритм не итерирует и не вызывается из строкового strcmp(), помня, что не следует повторно называть strlen(), предпочтительно возвращает false немедленно, если сравнение равенства исчерпывает «стог сена», перед «иглой». Честно говоря, если это раннее скрининговое интервью, то достаточно людей не смогут реализовать что-то подобное - очень правдоподобно, что это все, что им нужно, не вдаваясь в предварительные индексирующие или государственные машины.

Answer 4

Я думаю, что следующий должен добиться того, что вы собираетесь делать -

Int основной (INT ARGC, символ * ARGV []) {

string A, B; 
size_t pos; 

while (true) 
{ 
    cout << endl << "Enter string: "; 
    getline(cin,A); 
    cout << "Enter substring to find: "; 
    getline(cin,B); 
    if ((A.size() > 0) && (B.size() > 0)) 
    { 
     cout << "\"" << B << "\" is"; 
     if ((pos = find(A,B)) == string::npos) 
     { 
      cout << " not"; 
     } 
     cout << " a substring of \"" << A<< "\""; 
     if (pos != string::npos) 
     { 
      cout << ", found at index " << pos; 
     } 
     cout << endl; 
    } 
} 
return 0; 

}

Answer 5

Если вам интересно, посмотрите на chapter (PDF) Майкла Абраша на поиск строк в его «Черновой книге графического программирования». The rest of the book can be freely accessed here.

Он начинает с хорошей рутины в C, а затем улучшает его и реализует его в сборке. Хотя на самом деле я не рассматриваю вопрос интервью, я думаю, что большинство интервьюеров будут впечатлены объяснением того, как оптимизировать ваш ответ.

Answer 6

Вопрос не определяет результат, если B не встречается в A и не требует положения вхождения. Таким образом, можно с уверенностью предположить, что A содержит B. Следовательно, программа должна возвращать строку B, так как значение первого вхождения B в A будет равно B.

Я считаю, что большая часть требований к POSIX для Windows NT была построена на аналогичных принципах.

Answer 7

В java

упаковка com.salpe.DS;

общественного класса TestContainsString { государственной статической силы основных (String [] арг) {

char[] string1 = new char[] { 'a', 'b', 'c', 'd', 'e', 'x', 'f', 'g', 
      'e', 'x' }; 
    char[] string2 = new char[] { 'e', 'x' }; 

    char[] longerChar; 
    char[] shortChar; 

    if (string1.length > string2.length) { 

     longerChar = string1; 
     shortChar = string2; 

    } else { 
     longerChar = string2; 
     shortChar = string1; 
    } 

    int j = 0; 
    int totalOccurences = 0; 

    for (int i = 0; i < longerChar.length; i++) { 

     if (longerChar[i] == shortChar[j]) { 
      j++; 

     } else { 

      j = 0; 
     } 

     if ((j) == shortChar.length) { 
      System.out.println("Found"); 
      j = 0; 
      totalOccurences++; 
     } 
    } 

    System.out 
      .println(String.valueOf(shortChar) + " Found in " 
        + String.valueOf(longerChar) + " " + totalOccurences 
        + " times"); 

} 

}

Answer 8

Попробуйте использовать это:

public class client { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     System.out.println(poSubString("bac","ba")); 
    } 

    public static int poSubString(String a, String b){ 
     if (a.length()<b.length()) 
      return -1; 
     int pointerA=0; 
     int pointerB=0; 
     while(pointerA+b.length()<=a.length() && pointerB<b.length()){ 
      if (a.charAt(pointerA+pointerB)==b.charAt(pointerB)) 
       pointerB++; 
      else{ 
       pointerB=0; 
       pointerA++; 
      } 
     } 
     if (pointerB==b.length()) 
      return pointerA; 
     else 
      return -1; 
    } 

}