加载中…HDU 3901 Wildcard 2011 Multi-University Training Contest 7 - Host by ECNU
(2011-08-02 18:46:33)
标签：
hdu3901wildcardit |
分类： 杂题 |
题目描述：
给你两个字符串A，B，其中B的'*'表示任意长度，？表示一个长度的任意字符。问B有没有可能是A的子串。
解题报告：
无视掉*，按照*把B分段，每一段都尽量往A串的前面匹配，每次匹配从上次匹配结束的地方开始。如果都能匹配，就是。
匹配要用到KMP，由于有？，需要修改next函数和KMP，就是如果遇到？，就认为是相同即可。
还有一点，如果B的开头和结尾不是*，那么一定要和A的开头结尾匹配上。
代码如下：
int i =
1, len = strlen(str + 1);
next[1]
= 0;
int j =
0;
while(i
<= len)
{
if (j == 0 || str[i] == str[j]
|| str[i] == '?' || str[j] == '?')
{
i++;
j++;
//if (j != 0 &&
str[i] == str[j])
// next[i] = next[j];
//else
next[i] =
j;
}
else
j = next[j];
}
int i =
pos, j = 1, len1 = strlen(str + 1), len2 = strlen(str2 + 1);
while(i
<= len1 && j
<= len2)
{
if (j == 0 || str[i] ==
str2[j] || str2[j] == '?')
{
i++;
j++;
}
else j = next[j];
}
if (j
> len2) return i - len2;
else
return -1;
int
len2 = strlen(str2 + 1);
int
len1 = strlen(str1 + 1);
int num
= 0;
for(int
i = 1; i <= len2; i++)
if (str2[i] != '*')
num++;
if (num
> len1) return false;
bool
flag = true;
int aa
= 1, bb = 1;
int
stid = -1, edid = -1, edid2 = -1;
while(aa <= len1
&& bb <= len2)
{
if (str2[bb] == '*')
{stid = aa; break;}
if (str2[bb] != '?'
&& str1[aa] != str2[bb])
{flag = false; break;}
aa++; bb++;
}
if
(stid == -1) stid = aa;
//cout
<< stid
<< ' '
<< flag
<< endl;
if
(flag)
{
aa = len1, bb = len2;
while(aa >=
stid && bb >=
stid)
{
//cout << aa
<< ' '
<< bb
<< endl;
if (str2[bb] == '*')
{edid = aa; edid2 = bb; break;}
if (str2[bb] != '?'
&& str1[aa] != str2[bb])
{flag = false; break;}
aa--; bb--;
}
if (edid == -1)
{
edid = aa;
edid2 = bb;
}
}
if
(!flag) return false;
int cnt
= 1;
for(int
i = stid; i <= edid; i++)
fir[cnt++] = str1[i];
fir[cnt] = '\0';
cnt =
1;
for(int
i = stid; i <= edid2; i++)
sec[cnt++] = str2[i];
sec[cnt] = '\0';
return
true;
while(scanf("%s%s", str1 + 1, str2 + 1) !=
EOF)
{
if
(!init())printf("NO\n");
else
{
bool flag = true;
int pos = 1;
int len2 = strlen(sec + 1);
int cnt = 1;
for(int i = 1; i <= len2;
i++)
{
if (sec[i]
== '*')
{
if (cnt >
1)
{
str2[cnt] = '\0';
jeo(str2);
pos = kmp(pos, fir, str2);
if (pos == -1)
{
flag =
false;
break;
}
pos++;
cnt = 1;
}
}else
str2[cnt++] = sec[i];
}
if (flag) printf("YES\n");
else printf("NO\n");
}
}
return
0;
给你两个字符串A，B，其中B的'*'表示任意长度，？表示一个长度的任意字符。问B有没有可能是A的子串。
解题报告：
无视掉*，按照*把B分段，每一段都尽量往A串的前面匹配，每次匹配从上次匹配结束的地方开始。如果都能匹配，就是。
匹配要用到KMP，由于有？，需要修改next函数和KMP，就是如果遇到？，就认为是相同即可。
还有一点，如果B的开头和结尾不是*，那么一定要和A的开头结尾匹配上。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
int next[200000];
char str1[200000];
char str2[200000];
char fir[200000], sec[200000];
void jeo(char str[])
{
}
int kmp(int pos, char str[], char str2[])
{
}
bool init()
{
}
int main()
{
}
喜欢
0
赠金笔