题意：
一个串s，经过多次被覆盖，求最小的原串s.
思路：
将题目转换下，就是 一个串s的前缀能覆盖串r,且s本身是r的一个后缀.
做法是首先考虑s的前缀能够覆盖r, 则我们从串r开始, 依次比较,并且记录上一次完全匹配(长度与s相同)的位置idx.
当出现ri != sj时,令 j = nxt[j], (这样做,而不是直接令J=0,是为了保证模式串最短),因为可能是从头开始的. 继续比较,
直到 j = 0, 意味着无法匹配.则将上一次的完全匹配位置 idx+1到 i,添加到模式串s中, 然后更新模式串的next函数,因为我们已经知道了. s( 1, length ),
这个时候模式串变成 s(1,length+(i-idx)),则只需要更新 s(length+1,length+(i-idx))的next函数值即可.
当匹配完后, 这个时候的模式串s,并非一定会是 主串r的后缀. 例如 (aabbaa), 模式串s最终会得到abb, 但是其不是r的后缀.
我们可以知道最后一次完全匹配是在 4的位置, 则我们应该再将 (5,6)添加到模式串s中,然后就得到了 abbaa, 即为最终答案.
View Code
#include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<algorithm> using namespace std; typedef long long LL; const int N = 100; LL dp[10][N][N]; int Mod; int a[N], b[N], A[10]; LL res[N]; LL dfs( bool less, int length, int sum, int mod ){ if( length == 0 ) return less && (sum==Mod) && (mod==0); if( less && (dp[length][sum][mod]!=-1) ) return dp[length][sum][mod]; LL tmp = 0; for(int x = 0; x < 10; x++){ if( !less && (x>A[length-1]) ) break; tmp += dfs( less || (x<A[length-1]), length-1, sum+x, (mod*10+x)%Mod ); } if( less ) dp[length][sum][mod] = tmp; return tmp; } LL solve( int x ){//x本身不被计算 int tmp = x, L = 0; while( tmp ) A[L++] = tmp%10, tmp /= 10; //reverse( A, A+L ); LL tot = 0; return dfs( false, L, 0, 0 ); } int main(){ int t; scanf("%d", &t); for(int i = 0; i < t; i++) scanf("%d%d", &a[i], &b[i] ); memset( res, 0, sizeof(res)); for(Mod = 1; Mod < N; Mod++){ memset( dp, -1, sizeof(dp)); for(int i = 0; i < t; i++ ) res[i] += solve( b[i]+1 ) - solve( a[i] ); } for(int i = 0; i < t; i++) printf("Case %d: %lld\n", i+1, res[i] ); return 0; }