首页 > 试题广场 >

实现字通配符*

[编程题]实现字通配符*
  • 热度指数:5809 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
在Linux Shell命令下通配符'*'表示0个或多个字符, 现编写一段代码实现通配符'*'的功能,注意只需要实现'*', 不用实现其他通配符。

输入描述:
第一行输入通配字符串
第二行输入要匹配查找的字符串


输出描述:
输出所有匹配的字串起始位置和长度,每行一个匹配输出
如果不匹配,则输出 -1 0
如果有多个按照起始位置和长度的正序输出。
示例1

输入

shopee*.com
shopeemobile.com

输出

0 16

说明

0 起始位置,16长度
示例2

输入

*.com
shopeemobile.com

输出

0 16
1 15
2 14
3 13
4 12
5 11
6 10
7 9
8 8
9 7
10 6
11 5
12 4
示例3

输入

o*m
shopeemobile.com

输出

2 5
2 14
7 9
14 2
#include <bits/stdc++.h>
using namespace std;

string s, t;
set<int> S;

void DFS(int i, int j){
    if(j==t.length())
        S.insert(i);
    if(i==s.length())
        return;
    if(s[i]==t[j])
        DFS(i+1, j+1);
    else if(t[j]=='*'){
        DFS(i, j+1);
        DFS(i+1, j);
        DFS(i+1, j+1);
    }
    return;
}

int main(){
    cin>>t>>s;
    bool flag = false;
    for(int i=0;i<s.length();i++){
        if(s[i]==t[0] || t[0]=='*'){
            DFS(i, 0);
            if(!S.empty()){
                flag = true;
                for(set<int>::iterator it=S.begin();it!=S.end();it++)
                    if(*it>i)
                        cout<<i<<" "<<*it-i<<endl;
            }
            S.clear();
        }
    }
    if(!flag)
        cout<<-1<<" "<<0<<endl;
    return 0;
}

发表于 2020-01-15 01:29:52 回复(11)
c++抄的offer
#include<iostream>
#include<vector>
using namespace std;
int Core(string &str1, string &str2, int left, int right,int start, int len)
{
    int res = false;
    if(str1[left] == '\0')
    {
        cout << start << " " << len << endl; 
        return true;
    }
    if(str1[left] != '\0' && str2[right] == '\0') return false;
    //当通配字符不是*时候,判断两个个字符是否相等
    if(str1[left] != '*')
    {
        if(str1[left] != str2[right]) return false;
        else 
        {
           res = Core(str1, str2, left+1, right+1, start, len+1);
        }
    }
    //当通配字符是*时候,通配字符向后移动或者查找字符向后移动
    else
    {
        //这里要注意不能用||因为一旦第一个条件成立第二个条件不会被执行
        bool tem1 = Core(str1, str2, left+1, right, start, len) ;
        bool tem2 = Core(str1, str2, left, right+1,start, len+1);
        res = tem1||tem2;
            
    }
    return res;
}
int main()
{
    
    string str1;
    string str2;
    cin >> str1 >> str2;
    if(str1 == "*")
    {
        for(int i = 0; i < str2.size();i++)
        {
            for(int j = 1; j + i <= str2.size();j++)
            {
                cout << i << " " << j << endl;
            }
        }
        return 0;
    }
    bool res = false;
    for(int i = 0; i < str2.size();i++) 
    {
        if(Core(str1, str2, 0,i,i,0)) res = true;
    }
    if(!res) cout << -1 << " " << 0 << endl;
    return 0;
}

发表于 2019-08-04 15:28:22 回复(3)
暴力居然也可以过??一开始做的时候都没敢往上写,看了评论区才试了下居然过了??
#include<iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
bool check(string p,string s) {
    int len1=p.size();
    int len2=s.size();
    vector<vector<bool>> dp(len1+1,vector<bool>(len2+1,false)); //dp[i][j]表示p[0...i-1]和s[0...j-1]是否匹配
    dp[0][0]=true;
    for(int i=1;i<=len1;++i) {
        if(p[i-1]=='*')
            dp[i][0]=dp[i-1][0];
    }
    for(int i=1;i<=len1;++i) {
        for(int j=1;j<=len2;++j) {
            if(p[i-1]==s[j-1]) {
                dp[i][j]=dp[i-1][j-1];
            } else {
                if(p[i-1]=='*') {
                    dp[i][j]=dp[i-1][j] || dp[i][j-1];
                } else {
                    dp[i][j]=false;
                }
            }
        }
    }
    return dp[len1][len2];
}
int main()
{
    string p;
    cin>>p;
    string s;
    cin>>s;
    if(p.size()==0) {
        cout<<"-1 0"<<endl;
        return 0;
    }
    int len=s.size();
    if(p=="*") {
        for(int i=0;i<len;++i) {
            for(int j=1;i+j<=len;++j) {
                cout<<i<<" "<<j<<endl;
            }
        }
        return 0;
    }
    bool flag=false;
    for(int i=0;i<len;++i) {
        if(s[i]!=p[0] && p[0]!='*')
            continue;
        for(int j=1;i+j<=len;++j) {
            if(check(p,s.substr(i,j))) {
                cout<<i<<" "<<j<<endl;
                flag=true;
            }
        }
    }
    if(!flag)
        cout<<"-1 0"<<endl;
    return 0;
}


发表于 2021-07-04 17:28:24 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
    private static boolean match(String matchStr, String str, int matchIdx, int idx) {
        if (matchIdx == matchStr.length() && idx == str.length()) {
            return true;
        }
        if (idx >= str.length() && matchIdx < matchStr.length() && matchStr.charAt(matchIdx) == '*') {
            return match(matchStr, str, matchIdx + 1, idx);
        }
        if (matchIdx >= matchStr.length() || idx >= str.length()) {
            return false;
        }
        if (matchStr.charAt(matchIdx) != '*' && matchStr.charAt(matchIdx) != str.charAt(idx)) {
            return false;
        }
        boolean flag = false;
        if (matchStr.charAt(matchIdx) == '*') {
            flag = match(matchStr, str, matchIdx + 1, idx) || match(matchStr, str, matchIdx, idx + 1);
        }
        if (matchStr.charAt(matchIdx) == str.charAt(idx)) {
            flag |= match(matchStr, str, matchIdx + 1, idx + 1);
        }
        return flag;
    }
 
    private static List<Integer[]> getMatchPosAndLen(String matchStr, String str) {
        List<Integer[]> ans = new ArrayList<>();
        for (int i = 0; i < str.length(); ++i) {
            if (matchStr.charAt(0) != '*' && matchStr.charAt(0) != str.charAt(i)) {
                continue;
            }
            for (int j = i; j < str.length(); ++j) {
                if (matchStr.charAt(matchStr.length() - 1) != '*' && matchStr.charAt(matchStr.length() - 1) != str.charAt(j)) {
                    continue;
                }
                if (match(matchStr, str.substring(i, j + 1), 0, 0)) {
                    ans.add(new Integer[]{i, j - i + 1});
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(new Integer[]{-1, 0});
        }
        return ans;
    }
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        List<Integer[]> list = getMatchPosAndLen(matchStr, str);
        for (Integer[] arr : list) {
            System.out.println(arr[0] + " " + arr[1]);
        }
 
    }
}
暴力加略微剪枝,过了!
发表于 2020-02-14 01:44:18 回复(3)
参考了其他同仁的递归思路,之前用非递归的解法也能AC全部case,但是代码繁琐,还是递归的写法更简洁。

#include <string>
#include <iostream>
#include <set>    //需要使用有序的集合
using namespace std;

set<int> matchedPos;

void ExgrexMatch(string& pattern, int pos1, string& str, int pos2) {
    if(pos1 == pattern.length()) {    //str[j:pos2) 是匹配的
        matchedPos.insert(pos2);
    }
    if(pos2 == str.length()) {    //str结束
        return;
    }
    
    if(pattern[pos1] == str[pos2]) {    //匹配1个
        ExgrexMatch(pattern, pos1+1, str, pos2+1);
    }
    else if(pattern[pos1] == '*') {
        ExgrexMatch(pattern, pos1+1, str, pos2);    //*匹配0个字符
        ExgrexMatch(pattern, pos1+1, str, pos2+1);  //*匹配1个字符
        ExgrexMatch(pattern, pos1, str, pos2+1);    //*匹配多个字符
    }
    else {    // pattern[pos1] != '*' && pattern[pos1] != str[pos2]
        return;    //此路不匹配
    }
}

int main() {
    string pattern, str;
    cin >> pattern >> str;
    
    int len1 = pattern.length();
    int len2 = str.length();
    bool someMatched = false;
    for(int j = 0; j < len2; j++) {
        if(str[j] == pattern[0] || pattern[0] == '*') {
            ExgrexMatch(pattern, 0, str, j);
            if(!matchedPos.empty()) {
                someMatched = true;
                for(auto pos : matchedPos) {
                    if(pos > j) {    //*匹配0个字符的时候,pos-j为0,
                                     //此时不应输出
                        cout << j << " " << pos - j << endl;
                    }
                }
                matchedPos.clear();    //清除开始下一轮
            }
        }
    }
    if(!someMatched) {
        cout << -1 << " " << 0 << endl;
    }
    return 0;
}


发表于 2021-03-28 21:58:07 回复(5)
主要是分成了两部分,一个是匹配方法和另一个是输入匹配的两个字段找寻方法:

首先用两个双循环做两个匹配字段搜寻,匹配字段为输入的需要匹配的字段1与带星号的匹配字段2两个,当(字段1 的首位字母与字段2相同)||或者(字段2的首字母是“*”,字段1的末端字母与字段2末端其匹配)||或者(字段2的末端字母是“*”号,字段1的首段字母与字段2首段匹配)||或者(字段2长度只有1,且是“*”号)

当上述条件满足时进行这两个两个字段的匹配,匹配方法返回true和false。

匹配的代码可以参考leetcode原题,或者剑指offer 第52题“正则表达式匹配”。

每次匹配得到true,就把正确的答案输出。。直接输出不会超时。。
我一开始还是因为刷题的惯性思维想把他们放在一个set里面最后输出结果超时了。。

import java.util.*;
public class Main{
     
    public static boolean check(String str2,String str1){
        boolean[][] dp=new boolean[str2.length()+1][str1.length()+1];
        int rows=dp.length;
        int cols=dp[0].length;
        dp[0][0]=true;
        for(int i=1;i<cols;i++){
            if(str1.charAt(i-1)=='*'){
                dp[0][i]=dp[0][i-1];
            }
        }
         //这个几乎就是leetcode原题了,但是leetcode题太多了所以没找到
        // 剑指offer第52题的思路也是一样的
        for(int i=1;i<rows;i++){
            for(int j=1;j<cols;j++){
                if(str2.charAt(i-1)==str1.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else if(str1.charAt(j-1)=='*'){
                    dp[i][j]=dp[i-1][j]||dp[i][j-1];
                }
            }
        }
        return dp[rows-1][cols-1];
    }
     
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        String str1="";
        String str2="";
        while(sc.hasNext()){
            str1=sc.next();
            str2=sc.next();
        }
        //TreeSet<int[]> res=new TreeSet<>((a,b)->(a[0]==b[0]?a[1]-b[1]:a[0]-b[0]));
        int len2=str2.length();
        int len1=str1.length();
        int count=0;
        if(len1>=1){
        for(int i=0;i<len2;i++){
            for(int j=i;j<len2;j++){
                if(str2.charAt(i)==str1.charAt(0)&&str2.charAt(j)==str1.charAt(len1-1)){
                    if(check(str2.substring(i,j+1),str1)){
                        StringBuilder s=new StringBuilder();
                        s.append(i);
                        s.append(" ");
                        s.append(j-i+1);
                        System.out.println(s.toString());
                        count++;
                    }
                }else if(str1.charAt(0)=='*'&&(str2.charAt(j)==str1.charAt(len1-1)||len1==1)){
                    if(check(str2.substring(i,j+1),str1)){
                       StringBuilder s=new StringBuilder();
                        s.append(i);
                        s.append(" ");
                        s.append(j-i+1);
                        System.out.println(s.toString());
                        count++;
                    }
                }else if(str1.charAt(len1-1)=='*'&&(str2.charAt(i)==str1.charAt(0)||len1==1)){
                    if(check(str2.substring(i,j+1),str1)){
                        StringBuilder s=new StringBuilder();
                        s.append(i);
                        s.append(" ");
                        s.append(j-i+1);
                        System.out.println(s.toString());
                        count++;
                    }
                }
            }
        }
    }
          if(count==0) {
            System.out.print("-1 0");
        }
 
        /*if(res.size()<=0){
            System.out.print("-1 0");
        }else{
                   for(int[] temp:res){
            for(int j=0;j<temp.length;j++){
              if(j==temp.length-1){
                    System.out.print(temp[j]);
                  break;
                }
                System.out.print(temp[j]+" ");
            }
            System.out.print("\n");
        }
        }
        */
 
    }
}



编辑于 2020-12-10 11:24:57 回复(0)
Scanner scanner=new Scanner(System.in); String str1=scanner.nextLine(); String str2=scanner.nextLine(); String[] list = str1.split("\\*"); String s1=list[0]; String s2=list[1]; int begin=str2.indexOf(s1); while(begin!=-1){ int end=str2.indexOf(s2,begin);  while(end!=-1){
        System.out.println(begin+" "+(end+s2.length()-begin));  end=str2.indexOf(s2,end+1);  }
    begin=str2.indexOf(s1,begin+1); }
发表于 2020-07-29 20:39:19 回复(0)
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * 实现字通配符*
 *
 * @author WU Jiahui
 * @date 2020/07/28 11:24
 */


public class Main {
    static boolean found = false;

    public static void search(char[] target, char[] text, int begin, int targetCur, int textCur, Set<Integer> set) {
        if (targetCur == target.length
                || (textCur == text.length && targetCur == (target.length - 1) && target[targetCur] == '*')) {
            found = true;
            if (!set.contains(textCur - begin) && textCur != begin) {
                set.add(textCur - begin);
                System.out.printf("%d %d\n", begin, textCur - begin);
            }
            return;
        }

        if (textCur == text.length) {
            return;
        }

        if (target[targetCur] == '*') {
            search(target, text, begin, targetCur + 1, textCur, set);
            search(target, text, begin, targetCur + 1, textCur + 1, set);
            search(target, text, begin, targetCur, textCur + 1, set);
        } else if (target[targetCur] == text[textCur]) {
            search(target, text, begin, targetCur + 1, textCur + 1, set);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String targetStr = scanner.nextLine();
        String textStr = scanner.nextLine();
        char[] target = targetStr.toCharArray();
        char[] text = textStr.toCharArray();
        for (int i = 0; i < text.length; i++) {
            search(target, text, i, 0, i, new HashSet<>());
        }
        if (!found) {
            System.out.printf("%d %d\n", -1, 0);
        }
    }
}

发表于 2020-07-28 16:57:27 回复(0)
import sys

class Solution:
    def match(i, j):
        # Terminator:当t每个元素都匹配到
        if j == len(t):
            ans.add(i)
            # 千万不能忘记return
            return
        # 当前索引相等(小心越界)
        if i < len(s) and s[i] == t[j]:
            Solution.match(i + 1, j + 1)
        elif i < len(s) and t[j] == '*':
            # 1. 让*代表nothing
            Solution.match(i, j + 1)
            # 2. 让x代表s[i]
            Solution.match(i + 1, j + 1)
            # 2. 让*代表多个字符
            Solution.match(i + 1, j)
        return

if __name__ == "__main__":
    while True:
        # 读取第一行
        t = sys.stdin.readline().strip()
        if t == '':
            break
        s = input()
        # 存储答案
        ans = set()
        # 初始化没找到
        if_find = False
        # 定字符的开始坐标i
        for i in range(len(s)):
            if s[i] == t[0]&nbs***bsp;t[0] == '*':
                Solution.match(i, 0)
            if len(ans):
                if_find = True
                for last_index in sorted(ans):
                    if last_index > i:
                        print(i, last_index - i)
            ans.clear()
        if not if_find:
            print(-1, 0)

发表于 2020-07-21 17:07:22 回复(0)
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] pat = sc.next().toCharArray();
		char[] str = sc.next().toCharArray();
        int count=0;

		for (int i = 0; i < str.length; i++) {
			for (int j = i; j < str.length; j++) {
				// 匹配str[i..j]
				if (match(pat, str, 0, i, j)) {
					System.out.println( String.valueOf(i) + " " + String.valueOf(j - i + 1));
                    count++;
				}
			}
		}
        if(count==0){
            System.out.println("-1 0");
        }
	}

	public static boolean match(char[] pat, char[] str, int pIndex, int left, int right) {

		if (pIndex == pat.length && left > right) {
            //恰好匹配完
			return true;
        }
		if (left > right && pIndex != pat.length && pat[pIndex] != '*') {
			//pat过长
            return false;
		}
        if (pIndex == pat.length && right >= left) {
			// str过长
			return false;
		}
		// pIndex!=length
		else if (pat[pIndex] == '*') {
			if (left > right) {
				return match(pat, str, pIndex + 1, left, right);
			} else {
				return match(pat, str, pIndex, left + 1, right) || match(pat, str, pIndex + 1, left, right);
			}
		} else if (left <= right && pat[pIndex] == str[left]) {
			return match(pat, str, pIndex + 1, left + 1, right);
		} else if (left <= right && pat[pIndex] != str[left]) {
			return false;
		} else {
			return false;
		}
	}
}
应该是暴力过,递归处理*那挺巧妙的

发表于 2020-07-14 17:30:52 回复(0)
参考上面nbgao写的java代码。搞不懂,他的能通过,但是我我改成思路完全一致的Java代码就不通过。
修改了几个bug才通过的。

import java.util.*;
public class Main{
    private static ArrayList<Integer> list = new ArrayList<>();
    private static char [] t;
    private static char [] s;
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        String str1 = sc.nextLine();
        String str2 = sc.nextLine();
        t = str1.toCharArray();
        s = str2.toCharArray();
        int flag = -1;
        for(int i = 0; i< s.length; i++){
            if(s[i] == t[0] || t[0] == '*'){
                DFS(i,0);
                if(!list.isEmpty())flag = 1;
                for(Integer num:list){
                    //特殊情况:当t串的最后一个字符是*时
                    //例如t="*";s="shop"一种输出是(0,1)
                    //当i=0;j=0;时 运行到代码if(t[j]=='*')DFS(i,j+1) 
                    //比较s的当前字符与t中*的下一个字符,由于*就是最后一个字符
                    //j值为t.length时,i的值为0,得到的输出结果为(0,0)
                    if(t[t.length-1]=='*'){
                        System.out.println(i+" "+(num-i+1));
                    }else{
                        System.out.println(i+" "+(num-i));
                    }
                }
                list.clear();
            }
        }
        if(flag == -1){
            System.out.println(flag+" "+0);
        }
    }
//i遍历字符串s,j遍历模式串t
    private static void DFS(int i, int j){
        if(j == t.length){
            list.add(i);
            return;
        }            
        if(i == s.length)
            return;
        if(s[i] == t[j]){
            DFS(i+1,j+1);
        }else if(t[j] == '*'){
            //*代表0个字符,比较s的当前字符与t中*的下一个字符
            DFS(i,j+1);
            //*代表多个字符,比较s的下一个字符与t中*
            DFS(i+1,j);
            //DFS(i+1,j+1);
        }
        return;
    }
}


发表于 2020-07-14 13:26:01 回复(0)
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

string s, t;
set<int> q;

void dfs(int i, int j)
{
    if(j == s.size())  q.insert(i);
    if(i == t.size())  return;
    
    if(t[i] == s[j])  dfs(i+1, j+1);
    else if(s[j] == '*')
    {
        dfs(i, j+1);
        dfs(i+1, j);
        dfs(i+1, j+1);
    }
}

int main()
{
    cin >> s >> t;
    bool flag = false;
    for(int i = 0; i < t.size(); i++)
    {
        if(s[0] == '*' || s[0] == t[i])
            dfs(i, 0);
        if(q.size())
        {
            flag = true;
            for(auto x : q)
                if(x > i)  cout << i << ' ' << x-i << endl;
        }
        q.clear();
    }
    if(!flag)   cout << -1 << ' ' << 0 << endl;
    
    return 0;
}

发表于 2020-07-10 17:12:06 回复(0)
动态规划+适当剪枝即可AC,新人欢迎指导
def shipei(a,b):
    j=-1
    if a=='*':
        return True
    if '*' not in a:
        if len(a)!=len(b):
            return False
    for i in range(len(a)):
        j+=1
        if a[i]=='*':
            sp=False
            s=a[i+1::]
            for k in range(j,len(b)):
                sp=sp&nbs***bsp;shipei(s,b[k::])
            return sp
        else:
            if j<len(b):
                if a[i]!=b[j]&nbs***bsp;j>len(b):
                    return False
            else:
                return False
    return True
while True:
    try:
        str1=input()
        str2=input()
        n=0
        ans=[]
        sy=1
        x=str1[0]
        for i in range(len(str2)):
            if x==str2[i]&nbs***bsp;x=='*':
                for j in range(len(str2)):
                    if shipei(str1,str2[i:j+1]) and (j-i+1)>0:
                        sy=0
                        print(str(i)+' '+str(j-i+1))
        if sy==1:
            print('-1 0')
    except:
        break

发表于 2020-06-30 15:45:31 回复(2)
动态规划过不去,内存不足。建议直接上回溯。
发表于 2020-06-24 09:59:27 回复(0)
import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String pattern = sc.next();
        String str = sc.next();
        String[] pats = pattern.split("\\*");
        if(pattern.endsWith("*")){
            pats = Arrays.copyOf(pats,pats.length+1);
            pats[pats.length-1] = "";
        }
        if(pats.length >= 2){
            List<String> matches = new ArrayList<String>();
            int fromIndex = 0;
            while(true){
                boolean isEmpty = pats[0].equals("");
                int step = pats[0].equals("")?1:pats[0].length();
                int position = str.indexOf(pats[0],fromIndex);
                if(position > -1 && position < str.length()){
                    fromIndex = position + step;
                    matches = findNext(position, position + (isEmpty?0:step),1,pats, str, matches);
                }else{
                    break;
                }
            }
            if(matches.size() > 0){
                for(String s:matches){
                    System.out.println(s);
                }
            }else{
                System.out.println("-1 0");
            }

        }else if(pattern.equals("*")){
            for(int i =0 ; i<str.length(); i++){
                for(int j = i; j<str.length(); j++){
                    System.out.println(i+" "+(j-i+1));
                }
            }
        }else{
            System.out.println("-1 0");
        }

    }

    private static List<String> findNext( int startIndex, int fromIndex, int signIndex, String[] pats, String str, List<String> matches){
        fromIndex -= pats[signIndex].equals("")?1:0;
        while(true){
            int step = pats[signIndex].equals("")?1:pats[signIndex].length();
            int position = str.indexOf(pats[signIndex], fromIndex);
            if(position > -1 && position < str.length()){
                fromIndex = position + step;
            }else{
                break;
            }
            if(signIndex < pats.length -1){
                findNext(startIndex,fromIndex, signIndex+1,pats,str,matches);
            }else{
                matches.add(startIndex+" "+(position+step-startIndex));
            }
        }

        return matches;
    }
}
发表于 2020-06-22 10:39:24 回复(0)
隆盛科技斐林试剂复试了的答案加了点自己理解后的注释,下次见到了这题可以自己看看
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
  
public class Main {
    private static boolean match(String matchStr, String str, int matchIdx, int idx) {
        if (matchIdx == matchStr.length() && idx == str.length()) {
            return true;
        }
        //str匹配到最后一个字符了,matchIdx后面还有多个*的情况
        if (idx == str.length() && matchIdx < matchStr.length() && matchStr.charAt(matchIdx) == '*') {
           return match(matchStr, str, matchIdx + 1, idx);
        }
        if (matchIdx >= matchStr.length() || idx >= str.length()) {
            return false;
        }
        //匹配中出现了不同的字符
        if (matchStr.charAt(matchIdx) != '*' && matchStr.charAt(matchIdx) != str.charAt(idx)) {
            return false;
        }
        boolean flag = false;
        //匹配中对*处理,*能表示多个字符,所以idx + 1,直到到达str的最后一个字符
        if (matchStr.charAt(matchIdx) == '*') {
            flag = match(matchStr, str, matchIdx + 1, idx) || match(matchStr, str, matchIdx, idx + 1);
        }
        //匹配中两个字符串的字符相同的情况,用与或保证可以从false变回true
        if (matchStr.charAt(matchIdx) == str.charAt(idx)) {
            flag |= match(matchStr, str, matchIdx + 1, idx + 1);
        }
        return flag;
    }
  
    private static List<Integer[]> getMatchPosAndLen(String matchStr, String str) {
        List<Integer[]> ans = new ArrayList<>();
         //找到头尾都相等的情况
        for (int i = 0; i < str.length(); ++i) {
            //保证第一个字符相同
            if (matchStr.charAt(0) != '*' && matchStr.charAt(0) != str.charAt(i)) {
                continue;
            }
           
            for (int j = i; j < str.length(); ++j) {
                //保证最后一个字符相同
                if (matchStr.charAt(matchStr.length() - 1) != '*' && matchStr.charAt(matchStr.length() - 1) != str.charAt(j)) {
                    continue;
                }
                if (match(matchStr, str.substring(i, j + 1), 0, 0)) {
                    ans.add(new Integer[]{i, j - i + 1});
                }
            }
        }
        if (ans.size() == 0) {
            ans.add(new Integer[]{-1, 0});
        }
        return ans;
    }
  
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
         String matchStr = in.next();
        String str = in.next();
        List<Integer[]> list = getMatchPosAndLen(matchStr, str);
        for (Integer[] arr : list) {
            System.out.println(arr[0] + " " + arr[1]);
        }
  
    }
}


发表于 2020-06-14 12:14:42 回复(0)
# 将一楼的大佬的代码改写成了Python, all pass, 感谢
import sys
def DFS(i,j): 
    if j==len(t):
        S.add(i)
        return
    if i==len(s):
        return
    if s[i]==t[j]:
        DFS(i+1, j+1)
    elif t[j]=='*':
        DFS(i, j+1)
        DFS(i+1, j)
        DFS(i+1, j+1)
    return
while True:
    line = sys.stdin.readline().strip()
    if line == '':
        break
    t = line
    s = input()
    S = set()
    flag = False
    for i in range(len(s)):
        # i is the start idx of s
        # S includes all the end index it that s[i:it] matches t
        if s[i]==t[0] or t[0]=='*':
            DFS(i, 0)
        if len(S) != 0:
            flag = True
            for it in sorted(S):
                if it>i:
                    print(i,it-i)
        S.clear()
    if not flag:
        print(-1, 0)


编辑于 2020-03-14 00:27:20 回复(0)
对了88%,另外的case运行超时,估计算法不是太好,有人看看那边算法可以优化不:
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.useDelimiter("/n");
        String a = sc.nextLine();
        String b = sc.nextLine();
        int bit = 0;
        for(int i = 0; i<b.length();i++){
            for(int j =i+1;j<b.length()+1;j++) {
                String subS = b.substring(i,j);
                if((subS != null) && (!subS.equals("")) &&(stringinit(subS,a))) {
                    bit =1;
                    System.out.println(i+" "+(j-i));
                }
            }
        }
        if(bit==0) {
            System.out.println("-1 0");
        }
        }

        public static boolean stringinit(String sub,String a){
               String[] list = a.split("\\*");
               int index = 0;
               String tmp = sub;
               if((sub.charAt(0)!=a.charAt(0)) && (a.charAt(0)!='*')){
                   return false;
               }else if((sub.charAt(sub.length()-1)!=a.charAt(a.length()-1)) && (a.charAt(a.length()-1)!='*')){
                   return false;
               }else {
                   for (int i = 0; i < list.length; i++) {
                       int tmpindex = tmp.indexOf(list[i]);
                       if(tmpindex == -1){
                           return false;
                       }else{
                           tmp = tmp.substring(tmpindex+list[i].length());
                       }
                   }
               }
               return true;
        }


    }


编辑于 2019-12-03 18:05:01 回复(0)

抄了1楼的答案,有几个很大的坑

#include
#include
using namespace std;
// 这道题和剑指Offer124页题目类似
// 不同的是这个题要在递归的同时输出字符串长度
bool match(const string &str,const string &pattern, int str_pos, int pat_pos, int start, int len){
    if(pattern[pat_pos] == '\0'){
//        printf("%d %d\n", start, len);
        cout << start << " " << len << endl;
        return true;
    }
    if(pattern[pat_pos] != '\0' && str[str_pos] == '\0') return false;
    // 当前指针没有碰到*的情况
    if(pattern[pat_pos] != '*'){
        // 比较两个字符是否相等
        if(pattern[pat_pos] == str[str_pos]){
            // 转移到下一个状态
            return match(str, pattern, str_pos + 1, pat_pos + 1, start, len + 1); 
        } else{
            return false;
        }
    } else{ // 碰到了'*' 
        // 模式串可以镶嵌 
        bool b_status = match(str, pattern, str_pos, pat_pos + 1, start, len);
        bool a_status = match(str, pattern, str_pos + 1, pat_pos, start, len + 1);
        return a_status || b_status; 
    }
    return false;
}
int main(){
    string pattern;
    string str;
    cin >> pattern >> str;
    if(pattern == "*"){
        for(int i = 0; i < str.length(); i++){ // 枚举前面的端点 
            for(int j = 1; i + j <= str.length(); j++){ // 枚举长度 
//                printf("%d %d\n", i, j);
                cout<< i << " " << j << endl;
            }
        }
        return 0;
    } 
    bool succ = false;
    // 从前到后枚举字符串起始点
    for(int i = 0; i < str.length(); i++){
        if(match(str, pattern, i, 0, i, 0)) succ = true;
    } 
    if(!succ){
//        printf("%d %d", -1, 0);        
        cout<< -1 << " " << 0 << endl;
    }
}
  1. 递归传参要const string&否则超时
  2. b_status和a_status前后的顺序,控制整体打印的顺序,打印顺序不符合要求调整这里即可。
发表于 2019-08-05 18:31:40 回复(0)
class fun(): def __init__(self): # self.str1 = '*'  # self.str2 = 'shopeemoblie.com'  self.str1 = raw_input() self.str2 = raw_input() self.str1 = self.str1.split('*') self.position = [] self.ans = [] if len(self.str1)>1: self.get_position() # print self.position  self.get_ans() else: self.fun_error() if len(self.ans)>0: for i in self.ans: print i[0], i[1] else: self.fun_error() def get_position(self): for i in self.str1:
            temp = [] if len(i) == 0: for j in range(len(self.str2)):
                    temp.append(j) self.position.append(temp) else:
                tempp = self.str2.find(i, 0, len(self.str2)) while tempp != -1:
                    temp.append(tempp)
                    tempp = self.str2.find(i, tempp + len(i), len(self.str2)) self.position.append(temp) def get_ans(self): for i in self.position[0]:
            longs = [] self.is_ok(i,0,longs) if len(longs)>0: for j in longs: self.ans.append([i,j-i]) # print self.ans  return self.ans def is_ok(self,min,level,longs): for i in self.position[level+1]: if i >= int(min)+len(self.str1[level]): if level == len(self.str1) - 2: if len(self.str1[level+1])== 0:
                        longs.append(i + len(self.str1[level + 1])+1) else:
                        longs.append(i+len(self.str1[level+1])) else: self.is_ok(i,level+1,longs) def fun_error(self): print -1,0  exit(0)
test = fun()






发表于 2019-07-30 18:16:12 回复(2)