字符串计数

看上一个回答者的分享，去搜了一下KMP算法

1、KMP算法

参考视频：

https://www.bilibili.com/video/BV1AY4y157yL/?spm_id_from=333.337.search-card.all.click&vd_source=b083fff6d62a13669980aa04a482ae68

https://www.bilibili.com/video/BV1jb411V78H/?spm_id_from=333.337.search-card.all.click&vd_source=b083fff6d62a13669980aa04a482ae68

next数组求法：

2、尝试了 字符串匹配

import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:是two倩呀！
 * Data:2022-09-21
 * Time:18:30
 */
public class demo1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String ret = scanner.next();
        String str = scanner.next();//子串

        int[] next = new int[str.length()];
        //求next数组 求子串的最长前后缀匹配
        int i = 0;
        int j = 1;
        //求next数组
        while (j < str.length()) {
            if (str.charAt(i) == str.charAt(j)) {//如果匹配了,在最长匹配的基础上+1
                i++;
                next[j++] = i;
            } else {//不匹配
                if (i == 0) {//如果i==0了 肯定不存在以elem[i]为底的最长公共前后缀 因为str[0]之前没有元素  那么next[j]=0
                    j++;
                    next[i] = 0;
                } else { //找寻以j-1也就是i-1元素为底的最长字符匹配长度 看能不能在这个元素的基础之上 拼接j对应的元素
                    i = next[i - 1];
                }
            }
        }
        //求最长匹配
        j = 0;
        i = 0;
        while (i < ret.length() && j < str.length()) {
            if (ret.charAt(i) == str.charAt(j)) {
                i++;
                j++;
            } else {
                if (j == 0)
                    i++;
                else
                    j = next[j - 1];
            }
        }
        if (j == str.length())//匹配成功 输出主串中开始匹配的下标
            System.out.println(i - j);
        else
            System.out.println(-1);
    }
}

3、

4、对于这个题，例如abab 全部是循环元素时，翻转后不相同的个数就是循环周期，否则就是数组长度

import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String str = scanner.next();
            int[] next = new int[str.length()];
            int i = 0;
            int j = 1;
            int n=str.length();
            while (j < n) {
                if (str.charAt(i) == str.charAt(j)) {
                    i++;
                    next[j++] = i;
                } else {
                    if (i == 0)
                        j++;
                    else
                        i = next[i - 1];

                }
            }
            if (next[n - 1] != 0 && n % (n - next[n - 1]) == 0)
                System.out.println(n - next[n - 1]);
            else
                System.out.println(str.length());
        }
    }
}

利用KMP的nexts数组的思想，求出最小周期是多少

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		String string = scanner.next();
		char[] pattern = string.toCharArray();
		int n = pattern.length;
		int[] nexts = new int[n];
		nexts[0] = 0;
		int i = 1;
		int len = 0;
		while(i < n) {
			if(pattern[i] == pattern[len]) {
				len++;
				nexts[i] = len;
				i++;
			}
			else {
				if(len > 0) len = nexts[len - 1];
				else {
					nexts[i] = len;
					i++;
				}
			}
		}
		if(n % (n - nexts[n - 1]) == 0)
			System.out.println(n - nexts[n - 1]);
		else System.out.println(n);
	}
}