【noi 2.6_6252】带通配符的字符串匹配（DP）

题意：给出一个带有通配符（"?"可以代替一个字符，"*"可以代替零个或多个字符）的a字符串和一个不带通配符的b字符串，判断他们是否能够匹配。

解法：f[i][j]表示a串的前i个是否能和b串的前j个匹配。其中，"?"由f[i-1][j-1]推出，"*"由f[i-1][0~j]推出，便用一个变量p存这些状态。

疑问：我自认为可以写滚动数组的，可惜一直错，求助~ (＞_＜)

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 
 7 char s[25],ss[25];
 8 int f[25][25];
 9 
10 int main()
11 {
12     scanf("%s%s",s+1,ss+1);
13     int l=strlen(s+1),ll=strlen(ss+1);
14     memset(f,0,sizeof(f));
15     f[0][0]=1;
16     for (int i=1;i<=l;i++)
17     {
18      bool p=f[i-1][0];
19      if (s[i]=='*') f[i][0]=p;
20      for (int j=1;j<=ll;j++)
21      {
22        p|=f[i-1][j];
23        if (s[i]=='?'||s[i]==ss[j]) f[i][j]|=f[i-1][j-1];
24        if (s[i]=='*') f[i][j]|=p;
25      }
26     }
27     if (f[l][ll]) printf("matched");
28     else printf("not matched");
29     return 0;
30 }