首页 > 试题广场 > 实现字通配符*
[编程题]实现字通配符*
  • 热度指数:1448 时间限制: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
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 <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 回复(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 回复(1)
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
String string1=scanner.next();
String string2=scanner.next();
int head=0;
int length1=string1.length();
int length2=string2.length();
int sign=0;

if(string1.charAt(0)=='*'&&string1.length()==1){
for (int i=0;i<length2;i++){
for(int j=1;j<=length2-i;j++){
System.out.println(String.valueOf(i)+" "+String.valueOf(j));
}
}
}else {
while (head < length2) {
if (equal(head, string1, string2, 0)) sign = 1;
head++;
}

if (sign == 0) System.out.println("-1 0");
}
}
public static boolean equal(int head,String string1,String string2,int parent){
int offset1=0,offset2=parent;
while (offset1<string1.length()&&head+offset2<string2.length()){
if(offset1+1<string1.length()&&string1.charAt(offset1)=='*'&&string1.charAt(offset1+1)!=string2.charAt(head+offset2)){
offset2+=1;
}else if(string1.charAt(offset1)=='*'){
offset1+=2;
offset2+=1;
}else if(string1.charAt(offset1)==string2.charAt(head+offset2)){
offset1+=1;
offset2+=1;
}else {
return false;
}
}

if(offset1<string1.length())return false;
System.out.println(String.valueOf(head)+" "+String.valueOf(offset2));
if(offset1==string1.length()&&head+offset2<string2.length()){
equal(head,string1,string2,offset2);
}
return true;
}
}
编辑于 2019-06-28 17:10:09 回复(0)