5 ( KMP)

5 ( KMP)

5.1

5.1.1

.

This is nowcoder
redocwon si sihT

// public static String reverseString(String s){ int len=s.length(); char[] out=new char[len]; for (int i = 0; i < len; i++) { out[len-i-1]=s.charAt(i); } return new String(out); } // public static String reverseString1(String s) { return new StringBuilder(s).reverse().toString(); }

5.1.2

: abc abc ,abc cba,aabcd bcada;
s t t s

1: : s = anagram , t = nagaram
: true
2:

: s = rat , t = car
: false
:

// 1 public static boolean isAnagram(String s, String t) { if(s.length()!=t.length()){ return false; } char[] s1=s.toCharArray(); char[] t1=t.toCharArray(); Arrays.sort(s1); Arrays.sort(t1); return Arrays.equals(s1,t1); } // 2 public static boolean isAnagram1(String s, String t) { int[] flag=new int[128]; if(s.length()!=t.length()){ return false; } for (int i = 0; i <s.length() ; i++) { flag[(int)s.charAt(i)]++; } for (int i = 0; i < t.length(); i++) { int a=(int)t.charAt(i); flag[a]--; if(flag[a]<0){ return false; } } for (int a :flag) { if(a!=0){ return false; } } return true; }

5.1.3 %20

%20
( 1000)
string iniString int len, string

"Mr John Smith ,13
Mr%20John%20Smith
Hello World ,12
Hello%20%20World

// 2 public static String replaceSpace(String s){ return s.replaceAll("\\s","%20"); } // 1 public static String replaceSpace2(char[] s,int n){ int count=n; for (int i = 0; i < n; i++) { if(s[i]==' '){ count+=2; } } int p1=n-1; int p2=count-1; while (p1>0){ if(s[p1]==' '){ s[p2--]='0'; s[p2--]='2'; s[p2--]='%'; }else { s[p2--]=s[p1]; } p1--; } return new String(s,0,count); }

5.1.4

aabcccccaaa a2b1c5a3 a z

1:

aabcccccaaa
a2b1c5a3
2:

abbccd
abbccd
abbccd" "a1b2c2d1

[0, 50000]

public static String compressString(String S) { if (S.length()==0){ return ""; } int last=0; int count=1; StringBuilder sb=new StringBuilder(S.charAt(0)); for (int i =1; i < S.length(); i++) { if(S.charAt(i)==S.charAt(last)){ count++; }else{ sb.append(S.charAt(last)); sb.append(count); count=1; } last++; } sb.append(S.charAt(last)); sb.append(count); if(sb.length()<S.length()){ return sb.toString(); }else{ return S; } }

5.1.5

s1 s2, s2 s1 ( rotate) s1= AABCD s2=CDAA, true; s1= ABCD S2= ACBD false

s2 s1

s1.apend(s1)
s2

public static boolean checkRotate(String s1,String s2){ return new StringBuilder(s1).append(s1).toString().contains(s2); } System.out.println(checkRotate("AABCD","CDAA"));//true

796.

class Solution { public boolean rotateString(String A, String B) { if(A.length() != B.length()) return false; boolean result = new StringBuilder(A).append(A).toString().contains(B); return result; } }

5.1.6

+

class Solution { public String reverseWords(String s) { String[] strs = s.trim().split(" "); // StringBuilder res = new StringBuilder(); for(int i = strs.length - 1; i >= 0; i--) { // if(strs[i].equals("")) continue; // res.append(strs[i] + " "); // StringBuilder } return res.toString().trim(); // } }

5.2

www.bilibili.com/video/BV1E4

str1= BBC ABCDAB ABCDABCDABDE str2= ABCDABD

str1 str2, , -1

str1 i str2 j

  • str1[i] == str2[j]
    i++
    j++
  • str1[i]! = str2[j]
    i = i - (j - 1)
    j = 0
    i j 0
  • ( !)

public class ViolenceMatch { public static void main(String[] args) { // String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; int index = violenceMatch(str1, str2); System.out.println("index=" + index); } // public static int violenceMatch(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1Len = s1.length; int s2Len = s2.length; int i = 0; //i s1 int j = 0; //j s2 while (i < s1Len && j < s2Len) {// if(s1[i] == s2[j]) {// ok i++; j++; } else { // // str1[i]! = str2[j] i = i - (j - 1) j = 0 i = i - (j - 1); j = 0; } } // if(j == s2Len) { return i - j; } else { return -1; } } }

KMP

KMP

Str1 = BBC ABCDAB ABCDABCDABDE Str2 = ABCDABD

  • Str1 Str2

  • Str1 Str2

  • Str1 Str2

  • Str1 1 ( BCD D ABCDAB KMP )

  • Str2

  • D ABCDAB B 2
    = -
    6 - 2 4 4

  • 2 AB 0
    = 2 - 0
    2 2

  • A

  • C D
    = 6 - 2
    4

  • = 7 - 0
    7

?

ABCDABD

  • A 0
  • AB
    [A]
    [B]
    0
  • ABC
    [A, AB]
    [BC, C]
    0
  • ABCD
    [A, AB, ABC]
    [BCD, CD, D]
    0
  • ABCDA
    [A, AB, ABC, ABCD]
    [BCDA, CDA, DA, A]
    A 1
  • ABCDAB
    [A, AB, ABC, ABCD, ABCDA]
    [BCDAB, CDAB, DAB, AB, B]
    AB 2
  • ABCDABD
    [A, AB, ABC, ABCD, ABCDA, ABCDAB]
    [BCDABD, CDABD, DABD, ABD, BD, D]
    0

ABCDAB AB 2 AB AB 4 - AB

KMP

public class KMPAlgorithm { public static void main(String[] args) { String str1 = "BBC ABCDAB ABCDABCDABDE"; String str2 = "ABCDABD"; int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0] System.out.println("next=" + Arrays.toString(next)); int index = kmpSearch(str1, str2, next); System.out.println("index=" + index); //15 } /** * @param str1 BBC ABCDAB ABCDABCDABDE * @param str2 ABCDABD * @param next , [0, 0, 0, 0, 1, 2, 0] * @return -1 */ public static int kmpSearch(String str1, String str2, int[] next) { // for (int i = 0, j = 0; i < str1.length(); i++) { // str1.charAt(i) != str2.charAt(j), j //KMP , ... while (j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j - 1]; } if (str1.charAt(i) == str2.charAt(j)) { j++; } if (j == str2.length()) {// j = 3 i return i - j + 1; } } return -1; } // ( ) //ABCDABD ---> [0, 0, 0, 0, 1, 2, 0] public static int[] kmpNext(String dest) { // next int[] next = new int[dest.length()]; next[0] = 0; // 1 0 for (int i = 1, j = 0; i < dest.length(); i++) { // dest.charAt(i) != dest.charAt(j) next[j-1] j // dest.charAt(i) == dest.charAt(j) // kmp while (j > 0 && dest.charAt(i) != dest.charAt(j)) { j = next[j - 1]; } // dest.charAt(i) == dest.charAt(j) +1 if(dest.charAt(i) == dest.charAt(j)) { j++; } next[i] = j; } return next; } }