[编程题]子串模糊匹配
[编程题]子串模糊匹配
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32M，其他语言64M
从字符串string开始完整匹配子串sub，返回匹配到的字符个数。
sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到匹配的字符，则说明不能完整匹配。
如果能完整匹配，返回匹配到的字符个数，如果有多种匹配方式，返回匹配字符数最少的那个，如果不能完整匹配，返回-1
输入描述:
第一行输入字符串string，长度小于10000第二行输入子串sub，长度小于100
输出描述:
从string开头位置完整匹配sub，匹配到的字符个数。
输入例子1:
abcdefg
a?c
输出例子1:
3
输入例子2:
aabcddefg
a?c
输出例子2:
4
输入例子3:
aabcddefg
b?e
输出例子3:
-1
输入例子4:
aabcddefg
a?d
输出例子4:
5本人代码实现解法一（C++）：
#include<iostream>
using namespace std;
string s1,s2;
int len1,len2;
int fun(int index1,int index2)
{
while(index1<len1&&index2<len2)
{
if(s2[index2]!='?'&&s1[index1]!=s2[index2])
return -1;
if(index1-index2>3)
return -1;
if(s1[index1]==s2[index2])
{
index1++;
index2++;
continue;
}
if(s2[index2]=='?'&&s1[index1]!='\0')
{
if(s1[index1+1]==s2[index2+1])
{
int temp=0;
if((temp=fun(index1+1,index2+1))!=-1)
{
return temp;
}
else
{
return -1;
//index1++;
}
}
else
index1++;
}
}
if(index2!=len2)
{
return -1;
}
else
{
return index1;
}
}
int main()
{
cin>>s1>>s2;
len1=s1.length();
len2=s2.length();
if(len1==0||len2==0)
{
cout<<0<<endl;
return 0;
}
cout<<fun(0,0)<<endl;
//getchar();
return 0;
}
解法二：（python）
import re
class Solution():
def return_re_length(self, first_str, second_str):
second_str_re = second_str.replace("?","(.*?)")
number_wenhao = len(second_str) - len(second_str.replace("?",""))
try:
pattern = re.compile(r'{}'.format(second_str_re))
res = pattern.match(first_str)
#print(number_wenhao)
for i in range(1,number_wenhao+1):
if len(res.group(i)) == 0 or len(res.group(i)) > 3:
return -1
return len(res.group(0))
except:
return -1
s1 = input()
s2 = input()
test = Solution()
print(test.return_re_length(s1, s2))
[编程题]子串模糊匹配
[编程题]子串模糊匹配
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32M，其他语言64M
从字符串string开始完整匹配子串sub，返回匹配到的字符个数。
sub中如果出现'?'表示可以匹配一到三个除'\0'以外的任意字符。
如果sub还有找不到匹配的字符，则说明不能完整匹配。
如果能完整匹配，返回匹配到的字符个数，如果有多种匹配方式，返回匹配字符数最少的那个，如果不能完整匹配，返回-1
输入描述:
第一行输入字符串string，长度小于10000第二行输入子串sub，长度小于100
输出描述:
从string开头位置完整匹配sub，匹配到的字符个数。
输入例子1:
abcdefg
a?c
输出例子1:
3
输入例子2:
aabcddefg
a?c
输出例子2:
4
输入例子3:
aabcddefg
b?e
输出例子3:
-1
输入例子4:
aabcddefg
a?d
输出例子4:
5本人代码实现解法一（C++）：
#include<iostream>
using namespace std;
string s1,s2;
int len1,len2;
int fun(int index1,int index2)
{
while(index1<len1&&index2<len2)
{
if(s2[index2]!='?'&&s1[index1]!=s2[index2])
return -1;
if(index1-index2>3)
return -1;
if(s1[index1]==s2[index2])
{
index1++;
index2++;
continue;
}
if(s2[index2]=='?'&&s1[index1]!='\0')
{
if(s1[index1+1]==s2[index2+1])
{
int temp=0;
if((temp=fun(index1+1,index2+1))!=-1)
{
return temp;
}
else
{
return -1;
//index1++;
}
}
else
index1++;
}
}
if(index2!=len2)
{
return -1;
}
else
{
return index1;
}
}
int main()
{
cin>>s1>>s2;
len1=s1.length();
len2=s2.length();
if(len1==0||len2==0)
{
cout<<0<<endl;
return 0;
}
cout<<fun(0,0)<<endl;
//getchar();
return 0;
}
解法二：（python）
import re
class Solution():
def return_re_length(self, first_str, second_str):
second_str_re = second_str.replace("?","(.*?)")
number_wenhao = len(second_str) - len(second_str.replace("?",""))
try:
pattern = re.compile(r'{}'.format(second_str_re))
res = pattern.match(first_str)
#print(number_wenhao)
for i in range(1,number_wenhao+1):
if len(res.group(i)) == 0 or len(res.group(i)) > 3:
return -1
return len(res.group(0))
except:
return -1
s1 = input()
s2 = input()
test = Solution()
print(test.return_re_length(s1, s2))