当前位置:   article > 正文

KMP算法、计算器(一)、(二)_在线kmp算法

在线kmp算法


题目1——KMP算法

给定两个字符串str和match,长度分别为N和M,实现一个算法,如果字符串中含有子串match,则返回match在str中的开始位置,不含有则返回-1,若出现了多次,则按照升序输出所有出现位置。
要求:时间复杂度为O(n)。
示例
输入:acbc(第一行str) bc(第二行match)
输出:2

解题思路

KMP算法主要是用来做字符串匹配的,它是在我们挨个字符匹配的基础上改进的。举个例子,当母串为ababcababa,子串为ababa,设两个指针i和j分别指向母串和子串,当i指向c,j指向子串最后一个字符a的时候,我们发现出现不匹配现象,但是我们可以不用将i指向第二个字符,j指向第一个字符,重新匹配。我们可以不移动i指针,将j指针前移(下面代码中的next记录了j指针的转移)指向第三个字符开始重新匹配,因为我们可以发现前缀字符ab是已经在母串中匹配了的(子串中是有对称串的,),所以不用再重新从第二个字符匹配。这样可以大大节省时间。

代码实现

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;
public class Main{
    public static int[] getNext(String match){
        int n = match.length();
        int[] next = new int[n];
        next[0] = -1; //-1表示不存在最大前缀和最大 后缀
        int k = -1;
        for(int i=1;i<n;i++){
            //如果下一个字符不相同,那么往前回溯
            while(k>-1 && match.charAt(k+1) != match.charAt(i)){
                k = next[k];
            }
            if(match.charAt(k+1) == match.charAt(i))
                k++;
            next[i] = k;
        }
        return next;
    }
    public static ArrayList KMP(String str,String match){
        ArrayList<Integer> res = new ArrayList<Integer>();
        int[] next = getNext(match);
        int str_n = str.length();
        int match_n = match.length();
        int k = -1;
        for(int i=0;i<str_n;i++){
            while(k>-1 && match.charAt(k+1) != str.charAt(i))
                k = next[k]; //往前回溯
            if(match.charAt(k+1) == str.charAt(i))
                k++;
            if(k == match_n-1){
                res.add(i-match_n+1);
                //重新初始化,寻找下一个位置
                k = -1;
                i = i-match_n+1;
            }
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String match = in.readLine();
        if(str.length() < match.length())
            System.out.println(-1);
        ArrayList<Integer> res = KMP(str,match);
        if(res.size() == 0)
            System.out.println(-1);
        else{
            Collections.sort(res);
            for(int i=0;i<res.size();i++)
                System.out.print(res.get(i)+" ");
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

题目2——计算器(一)

给定一个字符串形式的表达式,请你实现一个计算器并返回结果,字符串中包含+,-,(,),保证表达式合法。
示例
输入:“1+2”
输出:3

解题思路

如果是数字,则更新当前数字tmp,其他情况将tmp重置为0;
如果是+/-,更新res+=sig*tmp,并重置tmo=0,sig根据+/-设置为1/-1;
如果是(,后面小括号里面的内容需要优先计算,所以暂时把之前的res和符号入栈,并重置res=0,sig=1;
如果是右括号,之前的结果出栈,并计算整个式子。

代码实现

import java.util.*;

public class Solution {
    public int calculate (String s) {
        Deque<Integer> num_st = new ArrayDeque<>();
        int tmp = 0;
        int sig = 1;  //符号位,加法是1,减法就是-1
        int res = 0;
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(c>='0' && c<='9')
                tmp = tmp*10 + (c-'0');
            else if(c == '+' || c == '-'){
                res += sig*tmp;  
                tmp = 0;
                if(c=='+') sig = 1;
                else sig = -1;
            }else if(c == '('){
                num_st.push(res);
                num_st.push(sig);
                sig = 1;
                res = 0;
            }
            else if(c == ')'){
                res += sig*tmp;
                tmp = 0;
                res *= num_st.pop();
                res += num_st.pop();
            }
        }
        if(tmp!=0)
            res += sig*tmp;
        return res;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

题目3——计算器(二)

给定一个字符串形式的表达式s,请你实现一个计算器并返回结果,除法向下取整。字符串中包含+,-,*,/,保证表达式合法。

示例
输入:“8*9-19”
输出:53

解题思路

从题目中我们可以得知,字符串中一共包含几种数据:数组,操作符±*/,对于这些操作来说又可以进一步细分,一元操作符(需要知道操作符右边的数字,比如+5,-4)和二元操作符(需要知道左右两边的操作数)。
所以我们可以利用栈,从左到右遍历字符串,如果是数组,则更新数字,如果是运算符,则按照运算符规则计算,并将结果重新入栈。

代码实现

import java.util.*;
public class Solution {
    public int calculate (String s) {
        String str = s+'$';
        Deque<Integer> st = new ArrayDeque<Integer>();
        char sig = '+'; //操作数之前的运算符
        int num = 0;
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(c>='0' && c<='9'){
                num = num*10 + (c -'0');  //数字则更新
            }else{
                if(sig == '+')
                    st.push(num); //加法则+num入栈
                else if(sig == '-')
                    st.push(-1*num); //减法则-num入栈
                else if(sig == '*')
                    st.push(st.pop()*num); //乘法,则栈顶为左操作数,出栈计算,结果重新入栈
                else if(sig == '/')  //除法,与乘法类似
                    st.push(st.pop()/num);
                sig = c; //更新运算符
                num = 0; //操作数置为0
            }
        }
        int res = 0;
        //栈内所有元素的和即为表达式的值
        while(!st.isEmpty()){
            res += st.pop();
        }
        return res;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/天景科技苑/article/detail/891034
推荐阅读
相关标签
  

闽ICP备14008679号