Codeforces Round #578 (Div. 2) E Compress Words

感想

ロリハのお勉強

問題

https://codeforces.com/contest/1200/problem/E

問題概要

複数の文字列を順番に接続していく。ただし、重なるような部分があれば重ねたまま連結する。
(例：'abcd' + 'bcdef' = 'abcdef' )('bcd' が重なる。)

解説

• ローリングハッシュと呼ばれるデータ構造（？）を使う
• ローリングハッシュとは　文字列をハッシュ値に変換することで、文字列比較をO(1)で行うというもの。

実装

• 何文字重なるのかを毎回調べて、重なる部分を除いて連結する。
• しかし、原因不明のTLE。
• ごちゃごちゃしているうちにACをとるが原因が不明のまま数時間が過ぎ......

typedef long long ll;
#define p(x) cout<<x<<endl;
#define pu(x) cout<<(x);
#define el cout<<endl;

string table[100005];
string ans = "";
ll B = 8191;
ll al,bl;
 
void solve(string b){
    string a = ans;
    unsigned long long ah = 0,bh = 0,t = 1;
    num = 0;
    ll roop = min(al,bl);
    for(int i=1;i<=roop;i++){
        ah = ah + t * a[al - i];
        bh = bh * B + b[i - 1];
        ah %= mod;
        bh %= mod;
        if(ah == bh){
            num = i;
        }
        t *= B;
        t %= mod;
    }
    return;
}
 
int main(){
    cin >> n;
    for(i=0;i<n;i++){
        cin >> table[i];
    }
    ans = table[0];
    al = ans.length();
    for(int i=0;i<n-1;i++){
        bl = table[i+1].length();
        solve(table[i+1]);
        //文字列を連結する
        ans = ans +  table[i+1].substr(num,bl-num);
        al += bl - num;
    }
    p(ans);
    return 0;
}

結論

原因は２つ。

ans = ans + table[i+1].substr(num,bl-num);

を

ans += table[i+1].substr(num,bl-num);

に直すのと、

string a = ans;

をやめるとTLEが直った。２つ目はまあ言われてみればという感じがする

まとめ

プログラミング何もわからん。