华为非AI方向笔试真题 7月1号【字符串压缩与模式验证】

字符串压缩与模式验证(C/Py/Java/Js/Go)题解华为笔试真题 7月1号 非AI方向第一题 100分题型题目内容给定一个字符串sss请你判断它是否由一个较短的字符串重复多次构成。如果可以输出最短的重复段字符串重复次数否则输出字符串本身。例如“abababababab” 可以由 “ababab” 重复222次得到输出ab2ab2ab2。“abcabcabcabcabcabcabcabcabc” 可以由 “abcabcabc” 重复333次得到输出abc3abc3abc3。“aaaaaaaaaaaa” 可以由 “aaa” 重复444次得到也可以由 “aaaaaa” 重复222次得到按照最短的字符串输出输出a4a4a4。“ababaababaababa” 无法由某个子串重复多次构成输出ababaababaababa。输入描述一个字符串sss仅包含数字000-999、小写字母aaa-zzz、大写字母AAA-ZZZ字符串长度1≤n≤1061 \le n \le 10^61≤n≤106。输出描述一段字符串s_news\_news_news_news\_news_new重复次数字符串长度1≤n≤1061 \le n \le 10^61≤n≤106。样例1输入aaabbb输出aaabbb说明它无法被分割成至少两个完全相同的部分。题解和思路思路实现思路kmp如果s是循环拼接说明整个字符串最长相同前缀后缀肯定是存在大于0(这就代表next[n-1]一定要 大于 0)。先说结论如果k next[n-1], (n % (n - k) 0)则说明 s[: n- k]就是循环子串。可以简单推导一下假设直接用x表示最小循环子串那么字符串一定为循环子串重复而来类似与xxxxx假设k个x这时候来分析末尾最长公共前缀后缀长度肯定为(k-1) * x。 对应上面方程(n k * x.size()) 计算出来的最小循环数组就为x,也肯定可以整除的。代码总体时间复杂为OnC#includeiostream#includevector#includestring#includeutility#includesstream#includealgorithmusingnamespacestd;// kmp 算法求next数组vectorintgetNext(string s){intns.size();vectorintnext(n,0);for(inti1;in;i){intjnext[i-1];while(j0s[i]!s[j]){jnext[j-1];}if(s[i]s[j]){j1;}next[i]j;}returnnext;}intmain(){string s;cins;intns.size();vectorintnextgetNext(s);intprefixLennext[n-1];// 是由部分子串重复循环拼接组成if(prefixLen0(n%(n-prefixLen)0)){string anss.substr(0,n-prefixLen);intrepeaten/(n-prefixLen);coutansrepeate;}else{couts;}return0;}Javaimportjava.util.*;publicclassMain{// kmp 算法求next数组publicstaticint[]getNext(Strings){intns.length();int[]nextnewint[n];for(inti1;in;i){intjnext[i-1];while(j0s.charAt(i)!s.charAt(j)){jnext[j-1];}if(s.charAt(i)s.charAt(j)){j;}next[i]j;}returnnext;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);Stringssc.next();intns.length();int[]nextgetNext(s);intprefixLennext[n-1];// 是由部分子串重复循环拼接组成if(prefixLen0(n%(n-prefixLen)0)){Stringanss.substring(0,n-prefixLen);intrepeatn/(n-prefixLen);System.out.print(ansrepeat);}else{System.out.print(s);}}}python# kmp 算法求next数组defgetNext(s):nlen(s)nxt[0]*nforiinrange(1,n):jnxt[i-1]whilej0ands[i]!s[j]:jnxt[j-1]ifs[i]s[j]:j1nxt[i]jreturnnxtdefmain():sinput()nlen(s)nxtgetNext(s)prefixLennxt[n-1]# 是由部分子串重复循环拼接组成ifprefixLen0and(n%(n-prefixLen)0):anss[:n-prefixLen]repeatn//(n-prefixLen)print(f{ans}{repeat},end)else:print(s,end)if__name____main__:main()Javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,(line){input.push(line);});rl.on(close,(){constsinput[0];// kmp 算法求next数组functiongetNext(s){constns.length;constnextnewArray(n).fill(0);for(leti1;in;i){letjnext[i-1];while(j0s[i]!s[j]){jnext[j-1];}if(s[i]s[j]){j;}next[i]j;}returnnext;}constns.length;constnextgetNext(s);constprefixLennext[n-1];// 是由部分子串重复循环拼接组成if(prefixLen0(n%(n-prefixLen)0)){constanss.substring(0,n-prefixLen);constrepeatn/(n-prefixLen);process.stdout.write(ansrepeat);}else{process.stdout.write(s);}});Gopackagemainimport(bufiofmtos)// kmp 算法求next数组funcgetNext(sstring)[]int{n:len(s)next:make([]int,n)fori:1;in;i{j:next[i-1]forj0s[i]!s[j]{jnext[j-1]}ifs[i]s[j]{j}next[i]j}returnnext}funcmain(){in:bufio.NewReader(os.Stdin)varsstringfmt.Fscan(in,s)n:len(s)next:getNext(s)prefixLen:next[n-1]// 是由部分子串重复循环拼接组成ifprefixLen0(n%(n-prefixLen)0){ans:s[:n-prefixLen]repeat:n/(n-prefixLen)fmt.Print(ans,repeat)}else{fmt.Print(s)}}