《编程之美》字符串移位包含问题
《编程之美》字符串移位包含问题,个人觉得这个问题也可以通过求模的方式获得,代码如下
??? ??? String src="AABCD"; //源字符串
??? ??? String des="AABC";//匹配字符串
??? ???
??? ??? char[] chsrc=src.toCharArray();
??? ??? char[] chdes=des.toCharArray();
??? ???
??? ??? for(int i=0;i<chsrc.length;i++){
??? ??? ??? ??? int j=i;
???? ??? ??? ??? for(;j<chdes.length+i;j++){
???? ??? ??? ??? ??? if(chdes[(j-i)%chsrc.length]!=chsrc[j%chsrc.length])break;? //依次匹配,大于的就求模
???? ??? ??? ??? }
???? ??? ??? ???
???? ??? ??? ??? if(j==(chdes.length+i))System.out.println("true");
??? ??? }
?
最差的情况也是O(n^2),当然这里的比较还可以根据《算法导论》中的字符串匹配优化算法来获取,可以将时间复杂度进一步降低