【数据结构与算法】十二字符串搜索

朴灿烈づ我的快乐病毒、 2022-07-27 14:52 176阅读 0赞

# **【数据结构与算法】十二 字符串搜索** #

# **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)

--------------------

# **最后** #

通过上面一些简单的讲解，  
相信朋友们已经知道其原理及特性了。  
本人能力有限,  
如发现错误或不合理欢迎指正…

--------------------