算法基础:周期串问题

前端之家收集整理的这篇文章主要介绍了算法基础:周期串问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
如果一个字符串可以由某个长度为k的字符串重复多次得到,我们说该串以k为周期。例如,abcabcabcabc以3为周期(注意,它也可以6和12为周期,结果取最小周期3)。

输入参数: 字符串

返回值: 字符串最小周期

代码实现:

package huawei

import (
	"bufio"
	"fmt"
	"os"
)

func Test1Base() {
	fmt.Println("Please input the res string:")
	//从控制台读取数据
	inputReader := bufio.NewReader(os.Stdin)
	s,err := inputReader.ReadString('\n')
	checkError(err,"Reading data from command line")
	//去除末尾换行符
	s = string(s[:len(s)-1])

	period := getMinPeriod(s)
	fmt.Println("period:",period)
}

//获取字符串最小周期
func getMinPeriod(s string) int {
	resChars := []rune(s)

	for count := 1; count <= len(resChars)/2; count++ {
		if checkPeriod(resChars[:count],resChars) {
			return count
		}
	}

	return -1
}

//判断testChars是否为resChars的一个周期,如abc是abcabcabc的一个周期
func checkPeriod(testChars []rune,resChars []rune) bool {
	testLen,resLen := len(testChars),len(resChars)
	//不是整数倍,直接返回false
	if resLen%testLen != 0 {
		return false
	}

	for i := testLen; i < resLen; i += testLen {
		if !checkSliceEqual(resChars[i:i+testLen],testChars) {
			return false
		}
	}

	return true
}

//判断两个slice的元素是否相同
func checkSliceEqual(a []rune,b []rune) bool {
	if len(a) != len(b) {
		return false
	}

	for i := 0; i < len(a); i++ {
		if a[i] != b[i] {
			return false
		}
	}

	return true
}

猜你在找的Go相关文章