UVa First Bangladeshi Contest of 2012-2013 Season Problem (B) Binary Substring

問題

A以上B以下の数で、
二進数で書いたとき、Pを二進数で書いた文字列を連続する部分文字列として含むような数のうち、最小のものを求めよ。
存在しない場合はNONEを出力せよ。

制約条件

1≦A, B, P≦10^15

方針

動的計画法+経路復元。
dp[i][j][k][l]を、i桁までで、
j = 1ならBより小になっていて、
k = 1ならAより大きくなっていて、
Pのl文字までマッチしているような状態に至れるかとする。

これを更新していくようなDPをすればいい。

Pを二進数で書いた文字列について、
KMPでfailureリンクを作って、l文字目でマッチが失敗したときに、
次のマッチの位置がどこになるのか求めておく。

ソースコード

int n, m;
string s, t, u;
int dp[70][2][2][70], *fail, next[70][2];

int *buildFail(const char *p) {
  int m = strlen(p);
  int *fail = new int[m+1];
  int j = fail[0] = -1;
  for (int i = 1; i <= m; ++i) {
    while (j >= 0 && p[j] != p[i-1]) j = fail[j];
    fail[i] = ++j;
  }
  return fail;
}

bool rec(int pos, int sml, int big, int match){
	int &res = dp[pos][sml][big][match];
	if(res >= 0) return res;
	
	if(pos == n) return res = match == m;
	
	res = 0;
	rep(i, 2){
		int ns = sml || i < t[pos] - '0';
		int nb = big || i > s[pos] - '0';
		if(!ns && i > t[pos] - '0') continue;
		if(!nb && i < s[pos] - '0') continue;
		int nm = next[match][i];
		res |= rec(pos + 1, ns, nb, nm);
	}
	return res;
}

int main()
{
	int CS;
	cin >> CS;
	rep(cs, CS){
		
		s.clear(); t.clear(); u.clear();
		
		ll a, b, p;
		cin >> a >> b >> p;
		while(b > 0) t.pb('0' + b % 2), b /= 2;
		n = t.size();
		rep(i, n) s.pb('0' + a % 2), a /= 2;
		while(p > 0) u.pb('0' + p % 2), p /= 2;
		
		reverse(all(s));
		reverse(all(t));
		reverse(all(u));
		
		m = u.size();
		fail = buildFail(u.c_str());
		rep(i, m) rep(j, 2){
			int k = i;
			while(k >= 0 && u[k] != '0' + j) k = fail[k];
			next[i][j] = k + 1;
		}
		next[m][0] = next[m][1] = m;
		
		memset(dp, -1, sizeof(dp));
		bool ok = rec(0, 0, 0, 0);
		ll ans = 0;
		
		if(ok){
			int sml = 0, big = 0, match = 0;
			rep(i, n){
				rep(j, 2){
					int ns = sml || j < t[i] - '0';
					int nb = big || j > s[i] - '0';
					if(!ns && j > t[i] - '0') continue;
					if(!nb && j < s[i] - '0') continue;
					int nm = next[match][j];
					if(dp[i + 1][ns][nb][nm]){
						ans *= 2; ans += j;
						sml = ns; big = nb; match = nm;
						break;
					}
				}
			}
		}
		printf("Case %d: ", cs + 1);
		
		if(!ok) puts("NONE");
		else cout << ans << endl;
		
		
		delete(fail);
	}
	return 0;
}