CF1200E Compress Words | 字符串hash

Examples

input 1

5

I want to order pizza

output 1

Iwantorderpizza

input 2

5

sample please ease in out

output 2

sampleaseinout

题意：如果前一个单词的后缀和第二个单词的前缀相同，那他们合并的时候省略前缀（看样例）。

题解：我们把前一个的后缀和后一个的前缀进行字符串hash，hash值一样的表示他们后缀和前缀相同可省略，用个pos标记第二个串从哪个位置开始要合并到前一个串上面，hash值相同时更新pos。

　　不知道为啥我用char数组写一直tle3，然后改成用string，结果wa1了？？？？显示 “wrong answer Unexpected EOF in the participants output”于是在输入n的时候加了个多组输入终于过了。

代码：

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e6 + ;

const ll P = ;

const ll mod = 1e9 + ;

string s,ans;

int main(){

    int n;

    while(~scanf("%d",&n)){

        ans="\0";

        while(n--) {

            cin>>s;

            int ls = s.size(),la = ans.size();

            int len = min(la,ls),pos = ;

            ll hs = ,ha = ,p = ;

            for (int i = ; i < len; i++) {

                ha = ((ans[la--i]*p%mod)+ha)%mod;

                hs = ((hs*P%mod)+s[i])%mod;

                if (ha == hs) pos = i+;

                p=p*P%mod;

            }

        ans+=s.substr(pos);

        }

        cout<<ans<<"\n";

    }

    return ;

}

巴特西

CF1200E Compress Words | 字符串hash

最新文章

热门文章