字符串

反转字符串

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

import java.util.*;
public class Solution {
    public String solve (String str) {
        char[] cstr = str.toCharArray();
        int len = str.length();
        for(int i = 0 ; i < len/2 ;i++)
        {
                char t = cstr[i];
                cstr[i] = cstr[len-1-i];
                cstr[len-1-i]=t;
        }
        return new String(cstr);
    }
}
//因为java中字符串是常量，只有用char数组实现；用其他语言实现的话这种方法无需额外空间。

//法2：利用辅助空间
import java.util.*;
public class Solution {
    public String solve (String str) {
        char[] ans = str.toCharArray();
        int len = str.length();
        for(int i = 0 ; i < len ;i++)
        {
                ans[i] = str.charAt(len-1-i);
        }
        return new String(ans);
    }
}

//利用库函数
import java.util.*;
public class Solution {
    public String solve (String str) {
        StringBuffer sb =new StringBuffer(str);//此方法针对的是io流，不能针对字符串。
        return sb.reverse().toString();
    }
}
//或者：
if(str==null||str.length()==0) return str;
return new StringBuilder(str).reverse().toString();

求子串位置

题目描述 easy 28

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
提示：字符串仅由小写英文字母构成
说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

朴素算法

记原串为ss,匹配串为pp。以ss中每个字符作为，每次从原串中的和匹配串的开始尝试匹配：

匹配成功：返回本次匹配的原串

匹配失败：从下一个继续匹配

class Solution {
  public int strStr(String ss, String pp) {
      int n = ss.length(), m = pp.length();
      char[] s = ss.toCharArray(), p = pp.toCharArray();
      // 枚举原串的「发起点」
      for (int i = 0; i <= n - m; i++) {//n=4，m=2，则主串只要到第三个就可以了
          // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
          int a = i, b = 0;
          while (b < m && s[a] == p[b]) {
              a++;
              b++;
          }
          // 如果能够完全匹配，返回原串的「发起点」下标
          if (b == m) return i;
      }
      return -1;
  }
}

kmp算法

视频：https://www.bilibili.com/video/BV1M5411j7Xx?from=search&seid=1940287345029268873
算法基本流程是原串是不会回溯的，每次借助next数组选择匹配串合适的位置开始往后匹配。

next数组

首先明确每次用匹配串匹配原串的时候，可能会发生部分匹配的情况，这时借助next数组可以减少不必要的重复匹配。next数组根据利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。

前缀：对于字符串aabaaf，是不包含f的所有子串。
后缀：是不包含第一个a的所有子串
最长相等前后缀: 对于aabaaf是0；即f对应的next数组值为0。完整版是010120
具体实现next数组时有的是将前缀表完整右移然后令第一个为-1（在f冲突时直接找f对应的下标）；有的是整体-1（冲突时还是看前一位，只不过会加回来）；有的原封不动（冲突时看f的前一位）。
原理*：
首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：
next数组构建：

对a，最长前后缀长度为0；对aa，最长前后缀长度为1；对aaa最长前后缀长度为2；对aaab，最长前后缀长度为0；

代码实现：

//本代码直接使用前缀表
//要明白一点，对于一个串aaab，前缀后缀都是有很多个的
//i:指向后缀末尾位置，同时表示当前求解的next数组位置，同时表示字符串最末位下标（指运行到的）。j指向前缀末尾位置，同时表示i之前（包括i）的子串的最长相等前后缀长度（即：j表示前缀长度-1）
//1.初始化 2. 前后缀相同 3.前后缀不同 4.next
//1.因为子串a没有前后缀，只能从aa开始初始化。故前缀结束位置j=0；后缀结束位置i=1；然后第一步前后缀相等进入3.。在aab时前后缀相同进入2.
//2.
public void getNext(char s[],int next[]){
    int j=0,i=1;
    next[0]=0;
    for(i=1;i<s.length;i++){
        while(s[i]!=s[j] && j>0){
            j = next[j-1];
        }
//后缀末位f!=前缀末位c，前缀长度减小(回退到上一轮的长度ab与bf同样不等，一直回退)
//这里说ab与bf不等只是便于理解，其实只用比较b与f不等即可
        if(s[i]==s[j]) j++;//相等则前后缀长度都加一，再比较两个是否相同
        next[i]=j;//长度变长之前要将当前字符对应的next更新到前缀的下一个位置。
//设字符串为abcabf，则当i指向b时：
//设j没有++前,最长前缀为ab(c) 最长后缀为ab(f);此时j指向第一个b，i指向第二个b
//容易发现，前后缀长度再度增加的话就会失配了（但现在并不知道
//在进行匹配时，若在f位置失配的话就需要回到c的位置开始重新匹配
//所以我们要在时f的前一个字符的next指向c。（因为我们每次调整都是用的上一个字符的next
//而c的位置就是j+1
    }
}

完整代码
class Solution {
    public int strStr(String haystack, String needle) {
        char[] p = needle.toCharArray();
        int m=needle.length();
        if(m==0) return 0;//空串返回-1
        int next[] = new int[m];
        char[] s = haystack.toCharArray();
        int n = haystack.length();
        getNext(p,next);//获得next数组
        for(int i=0,j=0;i<n;i++){
            if(s[i]==p[j]){
                j++;//若匹配则继续
            }else if(j>0)
            {
                j=next[j-1];
                i--;
                //若不匹配，则i不能后移
            }
            if(j==m) return i-m+1;//注意此处i是匹配的最后一个字符下标；减去长度+1则是起始下标
        }

        return -1;
    }
    public void getNext(char s[],int next[]){
    int j=0,i=1;
    next[0]=0;
    for(i=1;i<s.length;i++){
        while(s[i]!=s[j] && j>0){
            j = next[j-1];
        }
//后缀末位f!=前缀末位c，前缀长度减小(回退到上一轮的长度ab与bf同样不等，一直回退)
//这里说ab与bf不等只是便于理解，其实只用比较b与f不等即可
        if(s[i]==s[j]) j++;//相等则前后缀长度都加一，再比较两个是否相同
        next[i]=j;//长度变长之前要将当前字符对应的next更新到前缀的下一个位置。
//设字符串为abcabf，则当i指向b时：
//设j没有++前,最长前缀为ab(c) 最长后缀为ab(f);此时j指向第一个b，i指向第二个b
//容易发现，前后缀长度再度增加的话就会失配了（但现在并不知道
//在进行匹配时，若在f位置失配的话就需要回到c的位置开始重新匹配
//所以我们要在时f的前一个字符的next指向c。（因为我们每次调整都是用的上一个字符的next
//而c的位置就是j+1
    }
}
}

释：设P为子串，当next[j]已经求得，要求next[j+1]，可以分以下两种情况分析：

若子串中字符Pj等于Pi，显然next[i+1]=j+1。因为j为当前P最长相等前后缀长度。
若Pj不等于Pi，将Pi-j+1...Pi当作主串，将P1...Pj当作子串。类似于失配问题，需移动子串，即令j=next[j]，继续进行比较，若满足1.则求得next[j+1]。

计算机用此方法计算效率很高，但不利于手工计算和理解。

算法实现

实际编码时，通常我会往原串和匹配串头部追加一个空格（哨兵）。
目的是让j下标从0开始，省去j从-1开始的麻烦。

class Solution {
    // KMP 算法
    // ss: 原串(string)  pp: 匹配串(pattern)
    public int strStr(String ss, String pp) {
        if (pp.isEmpty()) return 0;
        // 分别读取原串和匹配串的长度
        int n = ss.length(), m = pp.length();
        // 原串和匹配串前面都加空格，使其下标从 1 开始
        ss = " " + ss;
        pp = " " + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
        int[] next = new int[m + 1];
        // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
        for (int i = 2, j = 0; i <= m; i++) {
            // 匹配不成功的话，j = next(j)
            while (j > 0 && p[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++
            if (p[i] == p[j + 1]) j++;
            // 更新 next[i]，结束本次循环，i++
            next[i] = j;
        }
        // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
        for (int i = 1, j = 0; i <= n; i++) {
            // 匹配不成功 j = next(j)
            while (j > 0 && s[i] != p[j + 1]) j = next[j];
            // 匹配成功的话，先让 j++，结束本次循环后 i++
            if (s[i] == p[j + 1]) j++;
            // 整一段匹配成功，直接返回下标
            if (j == m) return i - m;
        }
        return -1;
    }
}