给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
解：涉及子串不一定非要动态规划。
class Solution {
public:int strStr(string haystack, string needle) {if(needle.size()==0) return 0;if(haystack.size()==0) return -1;if(haystack.size()<needle.size()) return -1;/*//转化为找最长公共子串然后判断最长公共子串是不是needle，如果是的话，返回初始位置，如果不是的话，直接返回-1.int m=haystack.size();int n=needle.size();int dp[m+1][n+1];for(int i=0;i<=m;i++){for(int j=0;j<=n;j++){dp[i][j]=0;}}for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(haystack[i-1]==needle[j-1]){dp[i][j]=dp[i-1][j-1]+1;}//底下注释掉的是求最长公共子序列的dp数组。//else//{// dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];//}}}//不是长度，而是取这个子串时。int maxi=0;int maxj=0;for(int i=0;i<=m;i++){for(int j=0;j<=n;j++){if(dp[maxi][maxj]<dp[i][j]){maxi=i;maxj=j;}}}int count=dp[maxi][maxj];string str;for(int i=maxi-count+1;i<=maxi;i++){str+=haystack[i-1];}//不行，反了，要++才行。//while(count--)//{// str+=haystack[maxi-1];// maxi--;//}cout<<str<<endl;if(str==needle){return maxi-count;}else return -1;*/vector<string> strs;//用于存放所有位数为needle的子串。int n=needle.size();for(int i=0;i<haystack.size()-(n-1);i++){string str;for(int j=0;j<n;j++){str += haystack[i+j];}strs.push_back(str);}for(int i=0;i<strs.size();i++){cout<<strs[i]<<" ";if(strs[i]==needle)return i;//之所在存放时没有判断首位是不是needle[0]，是因为想保留这个相同的起始i，这样可以直接返回起点。}return -1;}};