|
题目链接
这个题目小样例用滑动窗口对每个单词进行判断是可以的过的，白嫖一时爽。
但是到大数据那里就死活过不了了，我确实没想到什么策略可以讲一下复杂度。不过我想过哈希，但是菜就菜在了不会处理。因为题目里写过了单词总长度不会超过10^5，疯狂暗示。
然后去看了官方题解，确实是利用了那个条件，不过，光是看题解那个思路我还是不知道该怎么写，关键的哈希我还是不会写。这里借鉴了大佬的哈希，真的涨姿势。秀的一批。
大佬链接
这里就不班门弄斧了，大佬思路很清晰。直接上代码了。
#include<bits/stdc++.h>
#include<functional>
using namespace std;
const int maxn = 102400;
struct word
{
char st,ed;
int num[26];
word(string s)
{
memset(num,0,sizeof(num));
int l = s.length();
st = s[0];
ed = s[l-1];
for(int i = 0;i < l;i++)
num[s[i]-'a']++;
//cout << s << endl;
}
bool operator == (const word &a) const
{
if(st!=a.st)
return false;
if(ed!=a.ed)
return false;
for(int i = 0;i < 26;i++)
if(num[i]!=a.num[i])
return false;
return true;
}
};
namespace std {
template<>
class hash<word>{
public:
size_t operator ()(const word &a)const{
hash<char> ch;
hash<int> it;
size_t ans = ch(a.st);
ans ^= ch(a.ed);
for(int i = 0;i < 26;i++)
{
ans ^= it(a.num[i]);
}
//cout << ans << endl;
return ans;
}
};
}
unordered_map<word,int> m;
int main()
{
int T;
cin >> T;
for(int kase = 1;kase <= T;kase++)
{
m.clear();
int ans = 0;
int L;
cin >> L;
set<int> len;
for(int i = 0;i < L;i++)
{
string s;
cin >> s;
m[word(s)]++;
//cout << s << " " << hc << endl;
len.insert(s.length());
}
long long a,b,c,d;
int n;
char s1[2],s2[2];
string s;
scanf("%s%s%d%lld%lld%lld%lld",s1,s2,&n,&a,&b,&c,&d);
s += s1[0];
s += s2[0];
int x0 = s[0];
int x1 = s[1];
int x2;
for(int i = 2;i < n;i++)
{
x2 = (x1 * a + x0 * b + c) %d ;
s += char(97 + ( x2 % 26 ));
x0 = x1;
x1 = x2;
}
//cout << s << endl;
for(auto &l:len)
{
word tmp(s.substr(0,l));
//cout << s.substr(0,l) << endl;
auto it = m.find(tmp);
if(it!=m.end())
{
ans += it->second;
m.erase(it);
//cout << hc<< endl;
}
//cout << ans << endl;
for(int j = l;j < n;j++)
{
tmp.num[s[j-l]-'a']--;
tmp.num[s[j]-'a']++;
tmp.st = s[j-l+1];
tmp.ed = s[j];
auto it = m.find(tmp);
if(it!=m.end())
{
ans += it->second;
m.erase(it);
//cout << hc<< endl;
}
//cout << ans << endl;
}
}
printf("Case #%d: %d\n",kase,ans);
}
return 0;
}
| 
转播
