leetcode_28題——Implement strStr()(KMPアルゴリズムを採用して、まだACがなくて、しかし自分のこちらのテストは間違いがありません)
2879 ワード
Implement strStr()
Total Accepted: 49294 Total Submissions: 223057 My Submissions
Question
Solution
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Update (2014-11-02):The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a
char * or String , please click the reload button to reset your code definition. Hide Tags
Two Pointers String
Have you met this question in a real interview?
Yes
No
Discuss
この問題は典型的なKMPアルゴリズムの文字列マッチングの問題ですが、なぜかACがなくて、まずマッチング値を計算して、それからKMPアルゴリズムを採用して、マッチング値を計算する時私が使った方法が複雑すぎるかもしれません.
だから時間を超えた
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*" " " " */
int public_str(string str)
{
if(str.size()==1||str.size()==0)
return 0;
int i=1,len=str.size();
for(i=1;i<len;i++)
{
int flag=0;
for(int j=0;j<i;j++)
{
if(str[j]!=str[len-i+j])
{
flag=1;
break;
}
}
if(flag==0)
return i;
}
return 0;
}
/* */
vector<int> match_value(string str)
{
vector<int> temp;
int len=str.size();
for(int i=0;i<len;i++)
{
string str1=str.substr(0,i+1);
temp.push_back(public_str(str1));
}
return temp;
}
/*KMP */
int strStr(string haystack, string needle) {
if(haystack.size()==0||needle.size()==0)
return -1;
if(needle.size()>haystack.size())
return -1;
vector<int> matchvalue=match_value(needle);
int len_haystack=haystack.size();
int len_needle=needle.size();
int i=0;
while(i<=(len_haystack-len_needle))
{
int flag=0;
int noMatch=0;
int j=0;
for(j=0;j<len_needle;j++)
{
if(needle[j]!=haystack[i+j])
{
flag=1;
noMatch=j;
break;
}
}
if(flag==0)
{
return i;
}
else if(flag==1)
{
if(j==0)
i=i+1;
else
i=i+j-matchvalue[j-1];
}
}
return -1;
}
int main()
{
string str="ABGTYDFSDFRTGAAASEDF";
string str1="TYD";
cout<<strStr(str,str1)<<endl;
}