算法基础:周期串问题
发布时间:2020-12-16 18:41:43 所属栏目:大数据 来源:网络整理
导读:如果一个字符串可以由某个长度为k的字符串重复多次得到,我们说该串以k为周期。例如,abcabcabcabc以3为周期(注意,它也可以6和12为周期,结果取最小周期3)。 输入参数: 字符串 返回值: 字符串最小周期 代码实现: package huaweiimport ("bufio""fmt""os
如果一个字符串可以由某个长度为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 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |