字符串压缩与模式验证(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_new，s_news\_news_new重复次数，字符串长度1≤n≤1061 \le n \le 10^61≤n≤106。

样例1

输入

aaabbb

输出

aaabbb

说明
它无法被分割成至少两个完全相同的部分。

题解和思路

思路

实现思路：kmp

1. 如果s是循环拼接，说明整个字符串最长相同前缀后缀肯定是存在大于0(这就代表next[n-1]一定要 大于 0)。
2. 先说结论如果k = next[n-1], (n % (n - k) == 0)则说明， s[: n- k]就是循环子串。
3. 可以简单推导一下
   1. 假设直接用x表示最小循环子串，那么字符串一定为循环子串重复而来，类似与xxxxx假设k个x
   2. 1. 这时候来分析末尾最长公共前缀后缀长度，肯定为(k-1) * x。 对应上面方程(n = k * x.size())， 计算出来的最小循环数组就为x,也肯定可以整除的。
4. 代码总体时间复杂为O（n）

C++

#include<iostream>#include<vector>#include<string>#include<utility>#include<sstream>#include<algorithm>usingnamespacestd;// kmp 算法求next数组vector<int>getNext(string s){intn=s.size();vector<int>next(n,0);for(inti=1;i<n;i++){intj=next[i-1];while(j>0&&s[i]!=s[j]){j=next[j-1];}if(s[i]==s[j]){j+=1;}next[i]=j;}returnnext;}intmain(){string s;cin>>s;intn=s.size();vector<int>next=getNext(s);intprefixLen=next[n-1];// 是由部分子串重复循环拼接组成if(prefixLen>0&&(n%(n-prefixLen)==0)){string ans=s.substr(0,n-prefixLen);intrepeate=n/(n-prefixLen);cout<<ans<<repeate;}else{cout<<s;}return0;}

Java

importjava.util.*;publicclassMain{// kmp 算法求next数组publicstaticint[]getNext(Strings){intn=s.length();int[]next=newint[n];for(inti=1;i<n;i++){intj=next[i-1];while(j>0&&s.charAt(i)!=s.charAt(j)){j=next[j-1];}if(s.charAt(i)==s.charAt(j)){j++;}next[i]=j;}returnnext;}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Strings=sc.next();intn=s.length();int[]next=getNext(s);intprefixLen=next[n-1];// 是由部分子串重复循环拼接组成if(prefixLen>0&&(n%(n-prefixLen)==0)){Stringans=s.substring(0,n-prefixLen);intrepeat=n/(n-prefixLen);System.out.print(ans+repeat);}else{System.out.print(s);}}}

python

# kmp 算法求next数组defgetNext(s):n=len(s)nxt=[0]*nforiinrange(1,n):j=nxt[i-1]whilej>0ands[i]!=s[j]:j=nxt[j-1]ifs[i]==s[j]:j+=1nxt[i]=jreturnnxtdefmain():s=input()n=len(s)nxt=getNext(s)prefixLen=nxt[n-1]# 是由部分子串重复循环拼接组成ifprefixLen>0and(n%(n-prefixLen)==0):ans=s[:n-prefixLen]repeat=n//(n-prefixLen)print(f"{ans}{repeat}",end="")else:print(s,end="")if__name__=="__main__":main()

Javascript

constreadline=require("readline");constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on("line",(line)=>{input.push(line);});rl.on("close",()=>{consts=input[0];// kmp 算法求next数组functiongetNext(s){constn=s.length;constnext=newArray(n).fill(0);for(leti=1;i<n;i++){letj=next[i-1];while(j>0&&s[i]!==s[j]){j=next[j-1];}if(s[i]===s[j]){j++;}next[i]=j;}returnnext;}constn=s.length;constnext=getNext(s);constprefixLen=next[n-1];// 是由部分子串重复循环拼接组成if(prefixLen>0&&(n%(n-prefixLen)===0)){constans=s.substring(0,n-prefixLen);constrepeat=n/(n-prefixLen);process.stdout.write(ans+repeat);}else{process.stdout.write(s);}});

Go

packagemainimport("bufio""fmt""os")// kmp 算法求next数组funcgetNext(sstring)[]int{n:=len(s)next:=make([]int,n)fori:=1;i<n;i++{j:=next[i-1]forj>0&&s[i]!=s[j]{j=next[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]// 是由部分子串重复循环拼接组成ifprefixLen>0&&(n%(n-prefixLen)==0){ans:=s[:n-prefixLen]repeat:=n/(n-prefixLen)fmt.Print(ans,repeat)}else{fmt.Print(s)}}