Beta Round #58-B: Tyndex.Brome
解法
二分探索するだけ。
感想
int ans=Lとしていたせいでかなりはまった。ソースはいろいろ手抜きをしていてかなり汚い。
const int MAX = 100005; const int INF = 1<<28; char str[MAX]; char input[2*MAX]; vector<int> cnts[0x100]; int N, K, L; void init(){ for(int i=0; i<0x100; i++){ cnts[i].push_back(-INF); cnts[i].push_back(-INF); } for(int i=0; str[i]; i++){ cnts[str[i]].push_back(i); } for(int i=0; i<0x100; i++){ cnts[i].push_back(INF); cnts[i].push_back(INF); } } inline int search(int n){ vector<int>::iterator itr = lower_bound(cnts[input[n]].begin(), cnts[input[n]].end(), n); int ans = INF; //not int ans = L; ans = min(ans, abs((*itr)-n)); ans = min(ans, abs((*(itr+1))-n)); ans = min(ans, abs((*(itr-1))-n)); return ans>MAX?L:ans; } int64 solve(){ int64 ret = 0; L = strlen(input); for(int i=0; input[i]; i++){ ret += search(i); } return ret; } int main(){ scanf("%d%d ",&N,&K); scanf("%s ",str); init(); while(N--){ scanf("%s ", input); cout << solve() << '\n'; } return 0; }