CF 314B: Sereja and Periods

題目連結：http://codeforces.com/contest/314/problem/B

題意：

對于字元串s和正整數n，規定[s,n]=s+s+……+s;

即  ["abc", 2] ="abcabc"

現給出w = [a, b] , q = [c, d]

求最大的p，使得 [q, p]是w的子序列

如無合法p，則輸出0

由于CF可以看代碼的緣故，一般不寫CF題解。

但是覺得這道題确實比較巧妙，于是記錄一下。

做這道題時參考了兩位神犇的代碼：

http://codeforces.com/contest/314/submission/3832474

http://codeforces.com/contest/314/submission/3845338

謝謝！

算法：

解法一：

預處理若從c串的第i位開始比對，

那麼在a串中最多可以循環比對c串的多少位。

解法二：

借用倍增的思想。

go[dep][get_id(i,j)]表示從字元串a的第i位，字元串c的第j位開始，比對字元串c的(2^dep)位後

.first表示兩個字元串比對後到達的位置

.second表示“消耗”了多少個a串

注意，很顯然在存在合法解的情況下

消耗a串的數量和c串的數量都不會超過int，

但是在不存在合法解的情況下，

.second初始化為INF，經過多次倍增可能會超過int

代碼如下：

解法一：

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MAXN=110;
char a[MAXN],c[MAXN];
int nxt[2][MAXN];

int main() {
    int b,d;
    scanf("%d%d",&b,&d);
    scanf("%s%s",a,c);
    int len1=strlen(a);
    int len2=strlen(c);
    for(int j=0; j<len2; j++) {
        int cur=j;
        nxt[0][j]=0;
        for(int i=0; i<len1; i++) {
            if(c[cur]==a[i]) {
                cur++;
                if(cur==len2) {
                    nxt[0][j]++;
                    cur=0;
                }
            }
        }
        nxt[1][j]=cur;
    }
    long long ans=0LL;
    int cur=0;
    for(int i=0; i<b; i++) {
        ans+=nxt[0][cur];
        cur=nxt[1][cur];
    }
    printf("%I64d\n",ans/d);
    return 0;
}
           

解法二：

#include<cstdio>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MAXN=110;
const int MAXM=30;
char a[MAXN],c[MAXN];
int len1,len2;
pair<int,long long> go[MAXM][MAXN*MAXN];

int get_id(int i, int j) {
    return i*len2+j;
}

long long solve(int dis) {
    int cur=get_id(0,0);
    long long cot=0;
    for (int i=0; i<MAXM; i++) {
        if(dis>>i&1) {
            cot+=go[i][cur].second;
            cur=go[i][cur].first;
        }
    }
    return cot;
}

int main() {
    int b,d;
    scanf("%d%d",&b,&d);
    scanf("%s%s",a,c);
    len1=strlen(a);
    len2=strlen(c);
    for(int i=0; i<len1; i++) {
        for(int j=0; j<len2; j++) {
            int id=get_id(i,j);
            go[0][id]=make_pair(id,INF);
            for(int k=0; k<len1; k++) {
                if(a[(i+k)%len1]==c[j]) {
                    go[0][id]=make_pair((get_id((i+k+1)%len1,(j+1)%len2)),(i==0)||((i+k)/len1));
                    break;
                }
            }
        }
    }
    for(int i=1; i<MAXM; i++) {
        for(int j=0; j<len1*len2; j++) {
            int nxt=go[i-1][j].first;
            go[i][j]=make_pair(go[i-1][nxt].first, go[i-1][j].second+go[i-1][nxt].second);
        }
    }
    int l=0;
    int r=INF;
    while(l<r) {
        int mid=(l+r+1)>>1;
        if(solve(mid)<=b) {
            l=mid;
        } else {
            r=mid-1;
        }
    }
    printf("%d\n",l/(len2*d));
    return 0;
}