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

Question

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

Answer 1

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

Answer 2

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

int main (int argc, char * 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 3

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

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

}

Answer 4

Википедия знает все

Answer 5

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

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

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

Answer 6

В java

пакет com.salpe.ds;

открытый класс TestContainsString {public static void main (String [] args) {

    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 7

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

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

Answer 8

Если вам интересно, взгляните на главу (PDF) Майкла Абраша о поиске строк в его "Черной книге по программированию графики". Остальная часть книги доступна здесь .

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