# Educational Codeforces Round 21 G. Anthem of Berland(dp+kmp)

fail可以用kmp进行预处理，将26个字母全部处理出来，这样复杂度就变成了26*n*m。

``` 1 #include<bits/stdc++.h>
2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
3 using namespace std;
4
5 const int N=1e5+7;
6 char s[N],t[N];
7 int s_len,t_len,now,nxt[N];
8 int dp[2][N],Nxt[26][N];
9
10 void kmp_pre(char x[], int m, int nxt[]) {
11     int i, j;  j = nxt[0] = -1;  i = 0;
12     while (i<m) {
13         while (-1 != j && x[i] != x[j])j = nxt[j];
14         nxt[++i] = ++j;
15     }
16 }
17
18 int main()
19 {
20     scanf("%s%s",s,t);
21     s_len=strlen(s),t_len=strlen(t);
22     if(s_len<t_len)return puts("0"),0;
23     kmp_pre(t,t_len,nxt);
24     F(j,0,25)F(k,0,t_len-1)
25     {
26         int idx=k;
27         while(idx!=-1&&(j+‘a‘)!=t[idx])idx=nxt[idx];
28         Nxt[j][k]=idx;
29     }
30     now=0;
31     F(j,0,t_len-1)dp[now][j]=-1;
32     dp[now][0]=0;
33     F(i,0,s_len-1)
34     {
35         F(j,0,t_len-1)dp[now^1][j]=-1;
36         if(s[i]==‘?‘)
37         {
38             F(j,0,25)F(k,0,t_len-1)if(dp[now][k]>=0)
39             {
40                 int idx=k,val=dp[now][k];
41                 if(idx!=-1&&(j+‘a‘)!=t[idx])idx=Nxt[j][idx];
42                 while(idx!=-1&&(j+‘a‘)!=t[idx])idx=nxt[idx];
43                 idx++;
44                 if(idx>=t_len)val++,idx=nxt[idx];
45                 dp[now^1][idx]=max(dp[now^1][idx],val);
46             }
47         }
48         else F(k,0,t_len-1)if(dp[now][k]>=0)
49         {
50             int idx=k,val=dp[now][k];
51             if(idx!=-1&&s[i]!=t[idx])idx=Nxt[s[i]-‘a‘][idx];
52             while(idx!=-1&&s[i]!=t[idx])idx=nxt[idx];
53             idx++;
54             if(idx>=t_len)val++,idx=nxt[idx];
55             dp[now^1][idx]=max(dp[now^1][idx],val);
56         }
57         now^=1;
58     }
59     int ans=0;
60     F(k,0,t_len)ans=max(ans,dp[now][k]);
61     printf("%d\n",ans);
62     return 0;
63 }```

## (KMP、dp)Codeforces Educational Codeforces Round 21 G-Anthem of Berland

Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem. Though there are lots and lots of victories in history of Berland, there is the one that stand out the most.

## Educational Codeforces Round 21 Problem F (Codeforces 808F) - 最小割 - 二分答案

Digital collectible card games have become very popular recently. So Vova decided to try one of these. Vova has n cards in his collection. Each of these cards is characterised by its power pi, magic number ci and level li. Vova wants to build a deck

## Educational Codeforces Round 21 Problem A - C

Problem A Lucky Year 题目传送门[here] 题目大意是说,只有一个数字非零的数是幸运的,给出一个数,求下一个幸运的数是多少. 这个幸运的数不是最高位的数字都是零,于是只跟最高位有关,只保留最高位,然后加一求差就是答案. Code 1 /** 2 * Codeforces 3 * Problem#808A 4 * Accepted 5 * Time:15ms 6 * Memory:0k 7 */ 8 #include<iostream> 9 #include<cstd

## Educational Codeforces Round 21 A-E题题解

A题      ............太水就不说了,贴下代码 #include<string> #include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<queue> #include<cstdio> using namespace std; int n,m; int m

## Educational Codeforces Round 18 C. Divide by Three DP

C. Divide by Three A positive integer number n is written on a blackboard. It consists of not more than 105 digits. You have to transform it into a beautiful number by erasing some of the digits, and you want to erase as few digits as possible. The n

## Educational Codeforces Round 36 (Rated for Div. 2)

Educational Codeforces Round 36 (Rated for Div. 2) F. Imbalance Value of a Tree You are given a tree T consisting of n vertices. A number is written on each vertex; the number written on vertex i is ai. Let's denote the function I(x,?y) as the differ