leecode 解题总结：28 Implement strStr()

#include <iostream>#include <stdio.h>#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <map>using namespace std;/*问题:Implement strStr().Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.分析：needle：针haystack:干草堆应该是返回字符串在另一个字符串首次出现的位置，如果没有返回-1.采用后缀树应该是可以做的：后缀树主要是产生n个后缀子串：分别是从第1个字符到第n个字符，第2个字符到第n个字符，...,第n个字符到第n个字符。【1】然后对每个后缀字符串，建立后缀树：需要一个位置数组记录从根节点到当前结点对应字符的子串出现的各个位置，返回的第一个位置就是。另外一种方式来查找最长重复子串：采用后缀数组的形式，比如字符串为"abcab"，仍然采用【1】中方式生成的后缀子串分别为:abcab,bcab,cab,ab,b对应子串起始位置为:0    ,1   ,2  ,3 ,4然后排序，得到:ab,abcab,b,bcab,cab发现：采用后缀数组不行，只能用后缀树来做，时间复杂度为O(n)。后缀结点包含：当前字符值，孩子结点，位置数组(26个字母组成，至少需要26个孩子结点)后缀树包含：后缀根节点，初始化存放字符串的函数，生成后缀子串，能够查找的函数，释放空间的函数输入:chaoma machaoma oachaoma ""chaoaom ao输出:4-1-12关键：1直接采用简单的方法：遍历主串所有可能的起始位置，然后查找与模式串是否相同2 后缀结点中，不是采用指针数组，而是采用<字符，指针>方式3 后缀树中生成采用递归方式4 class SuffixNode{public:	char _value;	//SuffixNode* _childs[CHILD_SIZE];//0~25是'a'~'z',26~51是'A'到'Z' = 	map<char , SuffixNode*> _childs;	vector<int> _positions;public:	SuffixNode(){}	SuffixNode(char value):_value(value){}	//根据给定的后缀子串，依次寻找到后缀子串中的下一个字符，然后如果该字符对应的结点没有生成就生成该结点，并记录其位置; 其实这里传入的肯定是根节点	void generateSuffix(string& str  , int pos)	{		_positions.push_back(pos);//易错，即使是空字符串，也需要保存位置，否则最后递归查找的是空串		if(str.empty() || pos < 0)		{			return;		}		char ch = str.at(0);		//如果当前字符对应的孩子结点没有，就新建该结点		if(_childs.find(ch) == _childs.end())		{			SuffixNode* node = new SuffixNode(ch);			_childs[ch] = node;		}		string remainder = str.substr(1);		//以当前新建的结点作为根节点继续处理		_childs[ch]->generateSuffix(remainder , pos);	}*/class Solution {public:    int strStr(string haystack, string needle) {		//如果都为空，返回0		if(haystack.empty() && needle.empty())		{			return 0;		}		//模式串为空，返回0		else if(needle.empty())		{			return 0;		}		//主串为空，返回-1，查找不到		else if(haystack.empty())		{			return -1;		}		int len1 = haystack.length();		int len2 = needle.length();		int i;		int j;		//只需要匹配到主串长度 - 模式串长度 + 1，因为主串中起始字符位置不可能超过该位置		for(i = 0 ; i < len1 - len2 + 1; i++)		{			for(j = 0 ; j < len2 ;)			{				//遍历到发现某个字符不等，直接换另一个起始字符				if(haystack.at(i + j) != needle.at(j))				{					break;				}				//找到起始相同的字符，判断后续是否相同				else				{					int tempPos = i + j;					while(j < len2 && haystack.at(i + j) == needle.at(j))					{						j++;					}					//如果此时j等于len2，说明找到，退出					if(j == len2)					{						return tempPos;					}				}			}		}		return -1;    }};void PRocess(){	string haystack;	string needle;	Solution solution;	while(cin >> haystack >> needle)	{		int pos = solution.strStr(haystack ,needle);		cout << pos << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}