首页 > 试题广场 > 实现字通配符*
[编程题]实现字通配符*
在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 回复(2)

抄了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)

热门推荐

通过挑战的用户

查看代码