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;
}