首页 > ACM题库 > HDU-杭电 > HDU 3259-Just Another String Matching Problem[解题报告]HOJ
2014
03-13

HDU 3259-Just Another String Matching Problem[解题报告]HOJ

Just Another String Matching Problem

问题描述 :

Given a text string T and a pattern P, your task is to count the number of nonempty substrings of T that matches P.
Note that we’re counting occurrences, so text ‘aa’ have two substrings that matches ‘a’, even though they’re the same.
Formally, a text T is a non-empty string of lowercase letters, a pattern P is a non-empty string of lowercase letters, question marks (?) and asterisks (*). A question mark matches exact one letter, an asterisk matches zero or more letters.

输入:

The first line contains a single integer T (T <= 50), the number of test cases.
Each case contains exactly two non-empty lines. The first line is the text, T, the second line is the pattern P. T will only contain lowercase letters while P will only contain
lowercase letters, question marks and asterisks. Neither of them can have more than 3000 characters.

输出:

The first line contains a single integer T (T <= 50), the number of test cases.
Each case contains exactly two non-empty lines. The first line is the text, T, the second line is the pattern P. T will only contain lowercase letters while P will only contain
lowercase letters, question marks and asterisks. Neither of them can have more than 3000 characters.

样例输入:

3
aa
a
abb
?b
aab
*b*

样例输出:

Case 1: 2
Case 2: 2
Case 3: 3

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN = 3005;
char s1[MaxN],s2[MaxN];
typedef long long LL;
LL dp[2][MaxN];

int main()
{
 //freopen("in.txt","r",stdin);
 int T,cas=0;scanf("%d",&T);
 while(T--)
 {
 scanf("%s%s",s1,s2+1);
 int n = strlen(s2+1), m = strlen(s1);
 bool ok = 1;
 for(int i = 1; i <= n; i++)if(s2[i]!='*')ok=0;
 if(ok)
 {
 printf("Case %d: %d\n",++cas,m*(m+1)/2);
 continue;
 }
 memset(dp, 0, sizeof(dp));
 for(int i = 0; i <= m; i++)dp[0][i]= 1;
 ok = 1;
 bool first = 1;
 for(int i = 1; i <= n; i++)
 {
 int p = i&1;
 int q = 1-p;
 if(s2[i]=='*')
 {
 dp[p][0] = dp[q][0];
 if(first)
 for(int j = 1; j <= m; j++)
 dp[p][j] = dp[p][j-1]+dp[q][j];
 else
 {
 LL mx = dp[q][0];
 for(int j = 1; j <= m; j++)
 {
 mx = max(mx, dp[q][j]);
 dp[p][j] = mx;
 }
 }
 first = 0;
 }
 else if(s2[i]=='?')
 {
 dp[p][0] = 0;
 for(int j = 1; j <= m; j++)
 dp[p][j] = dp[q][j-1];
 }
 else
 {
 dp[p][0] = 0;
 for(int j = 1; j <= m; j++)
 {
 if(s1[j-1]==s2[i])dp[p][j] = dp[q][j-1];
 else dp[p][j] = 0;
 }
 }
 //for(int j = 0; j <= m; j++)printf("dp[%d][%d]=%I64d\n",i,j,dp[p][j]);
 // memset(dp[q], 0, sizeof(dp[q]));
 }
 LL ans = 0;
 for(int i = 1; i <= m; i++)
 ans += dp[n&1][i];
 printf("Case %d: %I64d\n",++cas,ans);
 }

 return 0;
}