【データ構造とアルゴリズム】12文字列検索


【データ構造とアルゴリズム】12文字列検索
C++
#include <iostream>

using namespace std;

int searchStr(string source, string target){
    if(source.size() == 0 || target.size() == 0)
        return -1 ;

    if(source == target)
        return 0 ;

    char first = target[0] ;
    long max =  source.size()  - target.size() ;

    int i = -1 ;
    for( ; i <= max ; i++){
        while( ++i <= max && source[i] != first );    // Look for first character.

        if( i <= max){// Found first character, now look at the rest of v2
            int k = 0;
            for( ; source[i+k] == target[k] && k < target.size() ; k++ );

            if( k == target.size() )
                return i ;
        }
    }
    return -1 ;
}

int main(){

    cout << searchStr("", "") << endl;
    cout << searchStr("0123456789", "0123456789") << endl;
    cout << searchStr("1", "") << endl;
    cout << searchStr("1", "1") << endl;
    cout << searchStr("", "1") << endl;
    cout << searchStr("0123456789", "0") << endl;
    cout << searchStr("0123456789", "01") << endl;
    cout << searchStr("0123456789", "23") << endl;
    cout << searchStr("0123456789", "33") << endl;
    cout << searchStr("0123456789", "9") << endl;
    cout << searchStr("0123456789", "89") << endl;
    cout << searchStr("0808900089", "89") << endl;
    return 0;
}


まずtarget[0]を比較し、存在する場合は、その後の文字を比較する.
時間の複雑さ
O(mn)
最後に
上の簡単な説明を通じて、友达はすでにその原理と特性を知っていると信じています.私の能力は限られています.もし間違いを発見したり、不合理なことを発見したりしたら、指摘を歓迎します.