2022.11.19

2022.11.19

搞了搞我的博客园，（之前写是了些什么东西），搞了搞我的电脑。

不知道为什么博客园上的背景时有时无的，可惜了我那么好看的图。

哦！问题被 wxf 解决了。

想 AL 了。

不过要是 AL 在的话，今天是一定会考试的，奶茶也是一定不敢喝的。

也想去平邑的同学们了，没法见他们最后一面了。

没有午休，难过。

我把奶茶塞进了我的杯子袋里，下午上课的时候喝完了。

喝奶茶是真的会让人开心耶！

YCC 和字符串 hash 的极限拉扯。

就这么个小破东西。

！！！！！

自然溢出

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define orz cout << "AK IOI" <<"\n"
#define ull unsigned long long

using namespace std;
const int maxn = 1e4 + 10;
const int base = 131;

int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
void print(int X)
{
    if(X < 0) X = ~(X - 1), putchar('-');
    if(X > 9) print(X / 10);
    putchar(X % 10 ^ '0');
}
int Max(int a, int b){
    return a > b ? a : b;
}
int Min(int a, int b){
    return a < b ? a : b;
}
int n, ans = 1; 
ull a[maxn];
char s[1510];
ull hashh(char s[])
{
    int len = strlen(s);
    ull ans = 0; 
    for(int i = 1; i < len; i++)
        ans = ans * base + (ull)s[i];
    return ans;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n = read();
    for(int i = 1; i <= n; i++)
    {
        scanf("%s", s);
        a[i] = hashh(s);    
    }
    sort(a + 1, a + n + 1);
    for(int i = 2; i <= n; i++) if(a[i] != a[i - 1]) ans++;
    print(ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

双哈希

/*
Date:
Source:
knowledge:
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define orz cout << "AK IOI" <<"\n"

using namespace std;
const int base = 131;
const int maxn = 10010;
int mod1 = 19260817;
int mod2 = 19660813;

int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
    return x * f;
}
void print(int X)
{
    if(X < 0) X = ~(X - 1), putchar('-');
    if(X > 9) print(X / 10);
    putchar(X % 10 ^ '0');
}
int Max(int a, int b){
    return a > b ? a : b;
}
int Min(int a, int b){
    return a < b ? a : b;
}
int n, ans = 1;
char s[1510];
struct node{
    int x, y;
}a[maxn];
int hash1(char s[])
{
    int len = strlen(s), ans = 0;
    for(int i = 0; i < len; i++)
        ans = (ans * base % mod1 + s[i]) % mod1; 
    return ans;
}
int hash2(char s[])
{
    int len = strlen(s), ans = 0;
    for(int i = 0; i < len; i++)
        ans = (ans * base % mod2 + s[i]) % mod2; 
    return ans;
}
bool cmp(node a, node b)
{
    return a.x < b.x; 
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n = read();
    for(int i = 1; i <= n; i++)
    {
        scanf("%s", s); 
        a[i].x = hash1(s);
        a[i].y = hash2(s);
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 2; i <= n; i++)
    {
        if((a[i].x != a[i - 1].x) || (a[i].y != a[i - 1].y)) ans++;    
    }
    print(ans);
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

单哈希

/* 
Date:2022.11.19 
Source:LOJ 
knowledge:字符串hash 
*/ 
#include <cstdio> 
#include <iostream> 
#include <cstring> 
#define orz cout << "AK IOI" << "\n"; 
#define int long long 
using namespace std; 
const int maxn = 1e6 + 10; 
const int base = 133; 
const int mod = 998244353; 
inline int read() 
{ 
int x = 0, f = 1; char ch = getchar(); 
while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();} 
while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();} 
return x * f; 
} 
inline void print(int X) 
{ 
if(X < 0) X = ~(X - 1), putchar('-'); 
if(X > 9) print(X / 10); 
putchar(X % 10 ^ '0'); 
return ; 
} 
inline int Max(int a, int b){ 
return a > b ? a : b; 
} 
inline int Min(int a, int b){ 
return a < b ? a : b; 
} 
int la, lb, ans, num, sum[maxn], power[maxn]; 
char a[maxn], b[maxn]; 
void init() 
{ 
power[0] = 1; 
for(int i = 1; i <= maxn; i++) power[i] = power[i - 1] * base % mod; 
sum[0] = 0; 
for(int i = 1; i <= la; i++) sum[i] = (sum[i - 1] * base % mod + a[i] - 'A' + 1) % mod; 
for(int i = 1; i <= lb; i++) num = (num * base % mod + b[i] - 'A' + 1) % mod; 
} 
signed main() 
{ 
//freopen(".in", "r", stdin); 
//freopen(".out", "w", stdout); 
cin >> a + 1; cin >> b + 1; 
la = strlen(a + 1), lb = strlen(b + 1); 
init(); 
for(int i = 1; i <= la - lb + 1; i++) 
{ 
int num2 = (sum[i + lb - 1] - sum[i - 1] * power[lb] % mod + mod) % mod; 
if(num == num2) ans++; 
} 
printf("%lld", ans); 
//fclose(stdin); 
//fclose(stdout); 
return 0; 
}

图书管理

/*
Date:2022.11.19
Source:LOJ
knowledge:hash
*/
#include <cstdio>
#include <iostream>
#include <map>
#include <cstring>
#define orz cout << "AK IOI" << "\n";
#define int long long 

using namespace std;
const int mod = 998244353;
const int base = 13131;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int n; 
map <int, bool>mp; 
char opt[5], book[210];
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	n = read();
	while(n--)
	{
		cin >> opt;
		gets(book);
		if(opt[0] == 'a') 
		{
			int len = strlen(book), num = 0;
			for(int i = 0; i < len; i++) num = (num * base % mod + book[i] - 'A' + 1) % mod;
			mp[num] = 1;
		}
		else 
		{
			int len = strlen(book), num = 0;
			for(int i = 0; i < len; i++) num = (num * base % mod + book[i] - 'A' + 1) % mod;
			if(mp[num] == 1) puts("yes");
			else puts("no");
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

Power Strings

/*
Date:2022.11.19
Source:LOJ
knowledge:hash 
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#define orz cout << "AK IOI" << "\n";
#define int long long

using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int base = 13131;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
map<int, int> mp;
char a[maxn];
int power[maxn], sum[maxn];
void init()
{
	power[0] = 1;
    for(int i = 1; i <= maxn; i++) power[i] = power[i - 1] * base % mod;
}
signed main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);
	init();
	while(1)
	{
		cin >> a + 1;
		memset(sum, 0, sizeof sum);
		mp.clear(); 
		if(a[1] == '.') break; 
		int len = strlen(a + 1);
		for(int i = 1; i <= len; i++) sum[i] = (sum[i - 1] * base % mod + (int)a[i]) % mod;
		for(int l = 1; l <= len; l++)
		{
			if(len % l != 0) continue;
			int num = (sum[1 + l - 1] - sum[0] * power[l] % mod + mod) % mod;
			mp[num]++;
			for(int i = 1; i <= len - l + 1; i += l)
			{
				int flag = (sum[i + l - 1] - sum[i - 1] * power[l] % mod + mod) % mod;
				mp[flag]++;
			}
			if(mp[num] == ((len / l) + 1)) {print(len / l); puts(""); break;}
		}
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

KMP

写一次，学一次。

/*
Date:2022.11.19
Source:LUOGU
knowledge:KMP
*/
#include <cstdio>
#include <iostream>
#include <cstring> 
#define orz cout << "AK IOI" << "\n";

using namespace std;
const int maxn = 1e6 + 10;

inline int read()
{
	int x = 0, f = 1;  char ch = getchar();
	while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
	while(ch <= '9' && ch >= '0') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
inline void print(int X)
{
	if(X < 0) X = ~(X - 1), putchar('-');
	if(X > 9) print(X / 10);
	putchar(X % 10 ^ '0');
	return ;
}
inline int Max(int a, int b){
	return a > b ? a : b;
}
inline int Min(int a, int b){
	return a < b ? a : b;
}
int len1, len2, nxt[maxn], j;
char s1[maxn], s2[maxn];
void get_nxt()
{
	for(int i = 2; i <= len2; i++)
	{
		while(j > 0 && s2[j + 1] != s2[i]) j = nxt[j];
		if(s2[j + 1] == s2[i]) j++;
		nxt[i] = j;
	}	
}
int main()
{
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout); 
	cin >> s1 + 1 >> s2 + 1;
	len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);
	get_nxt();
	int j = 0;
	for(int i = 1; i <= len1; i++)
	{
		while(j > 0 && s1[i] != s2[j + 1]) j = nxt[j];
		if(s2[j + 1] == s1[i]) j++;
		if(j == len2)
		{
			print(i - len2 + 1); puts("");
			j = nxt[j];
		}
	} 
	for(int i = 1; i <= len2; i++) printf("%d ", nxt[i]);
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

原文地址：http://www.cnblogs.com/yangchengcheng/p/16906281.html