【データ構造とアルゴリズム】12文字列検索
【データ構造とアルゴリズム】12文字列検索
C++
まずtarget[0]を比較し、存在する場合は、その後の文字を比較する.
時間の複雑さ
O(mn)
最後に
上の簡単な説明を通じて、友达はすでにその原理と特性を知っていると信じています.私の能力は限られています.もし間違いを発見したり、不合理なことを発見したりしたら、指摘を歓迎します.
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)
最後に
上の簡単な説明を通じて、友达はすでにその原理と特性を知っていると信じています.私の能力は限られています.もし間違いを発見したり、不合理なことを発見したりしたら、指摘を歓迎します.