@[TOC](字符串_实现 strStr())

---

一、leetcode-151

实现 strStr()
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
输入：2
abcdefg

输出：fgabcde

---

二、题解

1.引库

 #include <iostream>#include <cstdio>#include <cstdlib>#include <queue>#include <stack>#include <algorithm>#include <string>#include <map>#include <set>#include <vector>using namespace std;

2.代码

最长公共前后缀
计算出前缀表
在字符串匹配算法中，尤其是 KMP 算法中，next 数组（或前缀表）用于表示每个前缀的最长相等前后缀的长度。将这个数组的值统一减一（即右移一位，使得初始位置为 -1）

class Solution {
public:void getNext(vector<int> &next,string &s){int j=-1;next[0]=j;for(int i=1;i<s.size();i++){// 注意i从1开始while(j>=0&&s[i]!=s[j+1]){j=next[j];}if(s[i]==s[j+1]){// 找到相同的前后缀j++;}next[i]=j;// 将j（前缀的长度）赋给next[i]}}int strStr(string haystack, string needle) {if(needle.size()==0) return 0;vector<int> next(needle.size());getNext(next,needle);int j=-1;for(int i=0;i<haystack.size();i++){while(j>=0&&haystack[i]!=needle[j+1]){j=next[j];}if(haystack[i]==needle[j+1]){j++;}if(j==needle.size()-1){return i-needle.size()+1;            }}return -1;}
};