关于字符串的一些东西（基础，马拉车，kmp）

一些基本操作(随便写写）

public class text {

        public static void main(String[] args) {
            String s;
            s="abcde";
            System.out.println(s.charAt(2));
            s.append("555");
            StringBuffer ss=new StringBuffer();
            ss.append("kk");
            s=ss.toString();
            char sss[]=s.toCharArray();
            s.replaceAll("K","FFF");

        }


}

马拉车
用来求最长回文子串

import java.util.Scanner;

public class Main {
        static int p[]=new int[23000000];
        static int res=0,las;
        static char ss[]=new char[23000000];
        public static void manachar(int len){
            int mx=0,id=0;
            for(int i=1;i<len;i++){
                if(i<mx) p[i]=Math.min(mx-i,p[2*id-i]);
                else p[i]=1;
                while(ss[i-p[i]]==ss[i+p[i]]) p[i]++;
                if(i+p[i]>mx){
                    mx=i+p[i];
                    id=i;
                }
                if(res<p[i]){
                    las=i;
                    res=p[i];
                }
            }
        }

        public static void main(String[] args) {
            Scanner jin=new Scanner(System.in);
            String s=jin.nextLine();
            int k=1;
            ss[0]='$';
            int len=s.length();
            for(int i=0;i<len;i++){
                ss[k++]='#'; ss[k++]=s.charAt(i);
            }
            ss[k++]='#';
            ss[k]='0';
            manachar(k);
            System.out.println(res-1);
        }
}

kmp
这种写法求next的时候错了一下位，next中的参数是原本String里的参数+1，这样第二次求的时候，j在next中做参数相当于自动减1了

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}