問題：
實作 strStr() 函數。
給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則傳回-1。
注意：當
needle
是空字元串時，我們應當傳回什麼值呢？這是一個在面試中很好的問題。
對于本題而言，當
needle
是空字元串時我們應當傳回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。
思路及代碼：
1. 我的做法：不多加分析地上來就暴力搜尋，沒有理清思路架構，多層循環容易出錯，此法不可取！尤其注意裡面的【邏輯Bug】
/* 我的思路：雙指針
*
* 代碼邏輯：1.定義兩個指針，分别指向haystack和needle，判斷*p =?= *q（表示“是否等于”）
* 2. 如果不相等，那麼p++，q指向needle開頭；如果相等，那麼p++，q++，逐位判斷。
*
* 邏輯Bug：例如"mississipi"和"issip"，在s1中查找s2時，檢查到s2的'p'時，s1到了第三個's'，
* 這時已經錯過了第二個'i'，是以将傳回-1，造成錯誤！
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int strStr(char* haystack, char* needle);
void main()
{
int result;
char s1[100]="mississippi";
char s2[50]="issip";
result=strStr(s1,s2);
printf("%d\n",result);
system("pause");
}
int strStr(char* haystack, char* needle)
{
if(strlen(needle)==0)
return 0; //needle為空時，傳回值為0（這與C語言的strstr()以及Java的indexOf()定義相符！）
if(strlen(haystack)==0)
return -1; //haystack為空時，傳回值為-1。
int loc=0,i=1,j=0; //表示needle首字母第一次出現;
int len2=strlen(needle); //C語言有求字元串長度的函數，頭檔案為<string.h>
char *p1=haystack,*p2=needle;
do
{
p2=needle; //如果不相等，那麼p2指向開頭
if(*p1!=*p2)
{
p1++;
loc++;
}
else
{
while(*p2!='\0'&&*p1==*p2)
{
p1++;
p2++;
loc++;
}
i++;
}
}while(*p1!='\0');
if(*p2=='\0')
{
loc=loc-len2; //最後一次*p1==*p2之後，loc又自加了一次，是以這裡不用減一！
return loc;
}
return -1;
}
2. 參考網友的代碼（一）：思路清晰，尤其循環嵌套做得很好，這種想法值得參考！
/* 代碼思路：數組
*
* 代碼邏輯：1.最大前提（最外層循環）：haystack剩下的長度 > needle的長度
* 2. 第二個前提（第二層循環）：haystack中存在needle[0]
* 3.第三層循環，haystack中存在needle[0]時，才移動指向needle的指針（此時移動才有意義）
*
* 巧妙之處：haystack中找到needle[0]時，指向haystack的指針并沒有移動，而是利用i+j的形式來調用haystack，這就避免了【錯過】的現象。
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int strStr(char* haystack, char* needle);
void main()
{
int result;
char s1[100]="mississippi";
char s2[50]="issip";
result=strStr(s1,s2);
printf("%d\n",result);
system("pause");
}
int strStr(char* haystack, char* needle)
{
int i,j,lenHay,lenNee;
lenHay = strlen(haystack);
lenNee = strlen(needle);
if(lenNee == 0) //如果needle長度為0，那麼傳回0。
return 0;
for(i=0;i<lenHay - lenNee + 1;i++)
//i<lenHay-lenNee+1的原因在于，如果lenHay剩下還未檢查的字元長度不如lenNee長，那麼在lenHay中将不存在lenNee（避免了很多運算）。
{
if(haystack[i] == needle[0]) //這裡的條件判斷可以省略很多不必要第二輪循環
{
for(j=0;j<lenNee;j++)
{
if(haystack[i+j] != needle[j]) /*這裡很巧妙，判斷滿足相等的條件時，沒有去
改變i的值，而是用i+j的方式，這就避免了【我的代碼】那個【錯過】的問題！*/
break;
}
if(j == lenNee)
return i;
}
}
return -1;
}
3. 參考網友的代碼（二）：
class Solution
{
/**
* 思路1
* 暴力破解，這個沒啥說的,挨個循環吧
* 耗時
* 執行用時 : 56 ms, 在Implement strStr()的PHP送出中擊敗了26.32% 的使用者
* 記憶體消耗 : 16.5 MB, 在Implement strStr()的PHP送出中擊敗了100.00% 的使用者
* 時間複雜度
* O(n)
*/
function strStr($haystack, $needle)
{
if (!$needle) {
return 0;
}
$length = strlen($needle);
$i = 0; // 短指針，指向比對字元串頭
while ($str = substr($haystack, $i, $length)) {
if ($str == $needle) {
return $i;
}
$i++;
}
return -1;
}
/**
* 思路2
* KMP 算法
* 利用已經部分比對這個有效資訊，保持i指針不回溯，通過修改j指針，讓模式串盡量地移動到有效的位置。
* 我這個寫的不太好，雖然時間上沒什麼大改變，不過接受了一種新思想。
* 具體算法示例
* 輸入 haystack = "hello world", needle = "orld"
* 1:循環 haystack 字元串,既然要找比對 'or' 的字元串,那麼開頭肯定是為 'o' 的。
* 根據這個，我們找到了下标為 5 的以 'o' 開頭的。
* 2:從 5 開始做循環比對，'o','w','o','r' 發現字元串不比對,需要重新尋找。
* 這時我們就沒必要在從 6 開始找，因為在處理比對字元串時，找到了另一個 'o' 的位置.
* 這樣我們就可以把下一次循環改變為 'o' 的位置，進而減少循環。
* 耗時
* 執行用時 : 28 ms, 在Implement strStr()的PHP送出中擊敗了42.11% 的使用者
* 記憶體消耗 : 16.5 MB, 在Implement strStr()的PHP送出中擊敗了100.00% 的使用者
* 時間複雜度
* O(n)
* 詳解
* https://www.cnblogs.com/yjiyjige/p/3263858.html
*/
function strStr($haystack, $needle)
{
if (!$needle) {
return 0;
}
$target_length = strlen($needle);
$length = strlen($haystack);
$i = 0;
while ($i <= $length) {
if ($length - $i < $target_length) {
return -1;
}
$str = '';
if ($haystack[$i] == $needle[0]) {
$kmp = 0;
for ($j = 0; $j < $target_length; $j++) {
$str .= $haystack[$i + $j];
if (($haystack[$i + $j] == $needle[0]) && !$kmp) {
$kmp = $i + $j + 1;
}
}
if
4. 自己編寫的最終版：
/* 參照網友二的思路，自己編寫的代碼 */
/* 解題思路：雙指針法？？（指針和數組索引有什麼不一樣？？？）
*
* 整體邏輯：1.定義兩個指針i,j分别指向兩個字元串
* 2.第一個大前提：haystack剩下的字元長度不能比needle長度小，不然傳回-1（避免很多計算）
* 3.第二個大前提：haystack中存在needle首字元
* 4.在上面兩個前提下，才對指向needle的指針進行自加操作
*
* 巧妙之處：haystack中找到needle[0]時，指向haystack的指針并沒有移動，而是利用i+j的形式來調用haystack，這就避免了【錯過】的現象。
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int strStr(char* haystack, char* needle);
void main()
{
int result;
char s1[100]="a";
char s2[50]="a";
result=strStr(s1,s2);
printf("%d\n",result);
system("pause");
}
int strStr(char* haystack, char* needle)
{
int len1,len2;
int i=0,j;
len1=strlen(haystack);
len2=strlen(needle);
if(len2==0)
return 0;
for(;i<=len1-len2;i++) //第一前提（巧妙之處：在haystack中找到needle的首字母之後，i不再自加，避免了我的思路中"mississip""issip"錯過第二個'i'的現象）
{
j=0; //每開始進行一次for循環，實質上是對needle首字元進行搜尋，是以每for一次，j要歸零。
if(haystack[i]==needle[0]) //第二前提
{
while(haystack[i+j]==needle[j]) //在兩個前提下，才進行判斷
{
j++;
if(j>=len2) //限制退出循環的條件（若不加退出條件，可正确執行，但會造成“溢出”）
break;
}
}
if(j==len2)
return i;
}
return -1;
}
![【20190419】【每天一道算法題】整數反轉（數學）問題：思路與代碼： 知識點：[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)