40分求调,都是因为第二个答案输出了0错的,但是找不到原因……
查看原帖
40分求调,都是因为第二个答案输出了0错的,但是找不到原因……
784295
1064940827wo楼主2023/8/2 00:33
//#define NDEBUG
#include<iostream>
#define MAXN 100005//较小最大值
#define MMAXN 10000005//较大最大值
#define INT_INF 0x7fffffff
using namespace std;
typedef struct e{
    int to,next;
}edge;
int main(){
    int n,m,hash,hashl=0,base=31,mod=1000005,sum[MMAXN],l=1;
    bool hashmap[MMAXN];
    int ans1=0,ans2=100000;
    string s,book[MAXN];
    cin>>n;
    for(int i=0;i<MMAXN;i++){
        hashmap[i]=false;
        sum[i]=0;
    }
    for(int i=0;i<n;i++){
        cin>>s;
        hash=0;
        for(int j=0;j<s.length();j++)hash=(hash*base+(s[j]-'a'))%mod;
        hashmap[hash]=true;
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>book[i];
        hash=0;
        for(int j=0;j<book[i].length();j++)hash=(hash*base+(book[i][j]-'a'))%mod;
        if(i==1){
            hashl=0;
            for(int j=0;j<book[l].length();j++)hashl=(hashl*base+(book[l][j]-'a'))%mod;
        }
        if(hashmap[hash])sum[hash]++;
        if(sum[hash]==1){
            ans1++;ans2=i-l+1;
        }
        while(l<=i){
            if(!hashmap[hashl]){
                l++;
                hashl=0;
                for(int j=0;j<book[l].length();j++)hashl=(hashl*base+(book[l][j]-'a'))%mod;
                continue;
            }
            if(sum[hashl]>=2){
                l++;
                sum[hashl]--;
                hashl=0;
                for(int j=0;j<book[l].length();j++)hashl=(hashl*base+(book[l][j]-'a'))%mod;
                continue;
            }
            break;
        }
        ans2=min(ans2,i-l+1);
    }
    cout<<ans1<<endl<<ans2;

    return 0;
}

2023/8/2 00:33
加载中...