java - 如何将while循环转换为for循环

Question

我正在使用 java 研究字符串匹配算法，我需要将 while 循环转换为 for 循环以便轻松处理它。

我需要将 KMPSearch 中的 while 循环转换为 for 循环 目的是在搜索过程开始之前检查要跳过的某些字符。 我不知道在哪里插入这部分代码

void KMPSearch(String txt, String pat) {

        int N=txt.length();
        int M=pat.length();
        int lps[]=new int[M];
        int j=0;// index of patt
        int i=0; //index of txt
        int c=0;
        computeLPS(lps,M,pat);
        //char [] skipChar=new char[] {'s','d','a','c'};

        while(i<N) {

            if(pat.charAt(j)==txt.charAt(i)) {
                i++;
                j++;
            }
            if(j==M) {
                System.out.println("pattern found at index  "+ (i-j-c));
                j=lps[j-1];

            }
            else if (i<N && pat.charAt(j) != txt.charAt(i)) {


                if (j != 0) {
                    j=lps[j-1];
                }
                else {
                    i=i+1;
                }

            }

        }


    }

Answer 1

如果我没理解错的话，您需要一个循环对 txt 中的每个字符执行一次迭代。您的循环可以这样重写:

    for (int i = 0; i < N; i++) {
        char ch = txt.charAt(i);
        /* Perform your potential char test here */
        while (j > 0 && (j == M || pat.charAt(j) != ch)) {
            if (j == M) {
                System.out.println("pattern found at index  "+ (i-j-c));
            }
            j = lps[j-1];
        }
        if (pat.charAt(j) == ch) {
            j++;
        }
    }

这不是完全相同的，因为理论上您的循环可以在新迭代开始时使用 j == M 进行迭代——这将导致错误。当发生这种情况时，上面的替代方案将继续内部 while 循环。但可能您的 lps 是这样的，您的代码也永远不会遇到这种情况。所以它们实际上是等价的。