HASH 60求助(5,7,8,9)未过
查看原帖
HASH 60求助(5,7,8,9)未过
166424
h_m_h楼主2021/4/9 14:03
#include<bits/stdc++.h>
using namespace std;
string s,st;
const long long p=197,mod1=1e9+7,mod2=1e9+9;
long long xb=0,first=0,hash1[1000007],sh,l,pow1=1,sum=0,ha1,f,ha2,hash2[1000009];
bool pd;
int main() 
{
    getline(cin,s);
    getline(cin,st);
    for (int i=0;i<s.size();++i)
    s[i]=tolower(s[i]);
    for (int i=0;i<st.size();++i)
    st[i]=tolower(st[i]); //转换小写
    long long l=s.size();
    for(int i=0;i<s.size();i++)
       sh=(sh*p%mod1+s[i]%mod1)%mod1;//子串hash值
    for(int i=1;i<=st.size();i++)
       hash1[i]=(hash1[i-1]*p%mod1+st[i-1]%mod1)%mod1;
    for(int i=1;i<=l;i++) 
       pow1=pow1*p%mod1;
    for(int i=1;i<=st.size();i++)
    {   
        first++;
        if(st[i]==' ')
        {
        	ha1=(hash1[i]-(hash1[i-l]*pow1)%mod1+mod1)%mod1;
            if(ha1==sh)
          {
          		sum++;
				if(pd==false) 
				{
					xb=first;
					pd=true;	
				}
          }
        }
	    
    }
    if(sum==0)cout<<-1;
    else cout<<sum<<" "<<xb-l;
      
    return 0;
}
2021/4/9 14:03
加载中...