2014
03-13

# 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;
}