[数据结构与算法]【C++】字符串对比查找

题目

题目解析

• 从源字符串中寻找是否包含所寻找的目标字符串，若不存在，返回-1；若存在，则返回字符串的起始位置
  
  

解题思路

1. 目标字符串长度 > 源字符串长度，即在源字符串中不存在匹配的目标字符串，返回-1；
2. 目标字符串不存在，返回0；
3. 目标字符串长度 < 源字符串长度，且源字符串中存在目标字符串
   ① 从0开始，目标字符串与源字符串一一对应，返回0；
   ② 从中间开始，在源字符串结束之前，可找到与目标字符串一一对应的字符，返回此时源字符串的位置-目标字符串的长度+1，即 i-j+1；
   ③从中间开始，在源字符串结束后与目标字符串不完全匹配，返回-1；
   
   

附加提示

• 字符串的长度函数：str.size()

详细代码

int strStr(string &source, string &target) 
{
// Write your code here
  // int flag = 0;
	if (source.size()<target.size()) return -1;
	else if (target.size() == 0) return 0;
	else
	{
       for(int i=0,j=0;i<source.size() && j<target.size(); )
       {
           if(source[i] == target[j])
           {
               i++;    
               j++;
           }
           else
           {
               i=i-j+1;
               j=0; 
           }
           if(i==j && j==target.size())    return 0;
           if(i==source.size() && j!=target.size())    return -1;
           if (j==target.size())   return i-target.size();
       }
   }
}