\(\qquad\!\!\)字符串算法……暂时就先这五种吧……
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P3370
【模板】字符串哈希
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<bits/stdc++.h>
#define in inline
#define re register
#define int long long
using namespace std;
const int N=10010;
const int M=1510;
int ba=4215,n,l,ans;
char a[N][M];
struct e
{
int m1,m2;
};
e z[N];
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
in int hash(char b[],int m)
{
int x=0;
for(re int j=1;j<=l;j++)
{
x+=(ba*x+b[j])%m;
}
return x;
}
in bool comp(e x,e y)
{
if(x.m1>y.m1)
{
return 1;
}
return 0;
}
signed main()
{
n=qread();
for(re int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
l=strlen(a[i]+1);
z[i].m1=hash(a[i]+1,1e9+7);
z[i].m2=hash(a[i]+1,1e9+9);
}
sort(z+1,z+n+1,comp);
ans=n;
for(re int i=1;i<=n;i++)
{
if(z[i].m1==z[i+1].m1&&z[i].m2==z[i].m2)
{
ans--;
}
}
qwrite(ans);
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P3375
【模板】KMP字符串匹配:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=1000010;
using namespace std;
int nxt[N];
int la,lb,j;
char a[N],b[N];
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
scanf("%s%s",a+1,b+1);
la=strlen(a+1);
lb=strlen(b+1);
for(re int i=2;i<=lb;i++)
{
while(j&&b[i]^b[j+1])
{
j=nxt[j];
}
if(b[j+1]==b[i])
{
j++;
}
nxt[i]=j;
}
j=0;
for(re int i=1;i<=la;i++)
{
while(j&&b[j+1]^a[i])
{
j=nxt[j];
}
if(b[j+1]==a[i])
{
j++;
}
if(j==lb)
{
qwrite(i-lb+1);
putchar('\n');
j=nxt[j];
}
}
for(re int i=1;i<=lb;i++)
{
qwrite(nxt[i]);
putchar(' ');
}
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P3805
【模板】manacher算法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=30000010;
using namespace std;
char b[N];
int dp[N],r,pos,ans=1;
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
scanf("%s",b+1);
int l=strlen(b+1);
for(re int i=l;i>=1;i--)
{
b[i<<1]=b[i];
b[(i<<1)|1]='#';
}
b[0]='#';
b[1]='#';
l=((l<<1)|1);
for(re int i=1;i<=l;i++)
{
if(i>r)
{
pos=i;
dp[i]=1;
while(b[i-dp[i]]==b[i+dp[i]])
{
dp[i]++;
}
r=i+dp[i]-1;
ans=max(ans,dp[i]-1);
continue;
}
int k=r-i+1;
if(dp[(pos<<1)-i]<k)
{
dp[i]=dp[(pos<<1)-i];
}
else if(dp[(pos<<1)-i]>k)
{
dp[i]=k;
}
else
{
pos=i;
dp[i]=k;
while(b[i-dp[i]]==b[i+dp[i]])
{
dp[i]++;
}
r=i+dp[i]-1;
}
ans=max(ans,dp[i]-1);
}
qwrite(ans);
putchar('\n');
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P2580
于是他错误的点名开始了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=500010;
using namespace std;
int n,m;
int cnt;
int t[N][26],f[N][26];
string a;
map<string,int> b;
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void js(re string x)
{
int l=x.length();
int k=0;
for(re int j=0;j<l;j++)
{
if(!t[k][a[j]-'a'])
{
t[k][a[j]-'a']=++cnt;
}
k=t[k][a[j]-'a'];
if(j==l-1)
{
f[k][a[j]-'a']++;
}
}
return ;
}
in void pd(re string x)
{
int l=x.length();
int k=0;
for(re int j=0;j<l;j++)
{
if(!t[k][a[j]-'a'])
{
printf("WRONG\n");
return ;
}
k=t[k][a[j]-'a'];
if(j==l-1)
{
if(f[k][a[j]-'a'])
{
printf("OK\n");
return ;
}
else
{
printf("WRONG\n");
return ;
}
}
}
}
int main()
{
n=qread();
for(re int i=1;i<=n;i++)
{
cin>>a;
js(a);
}
m=qread();
for(re int i=1;i<=m;i++)
{
cin>>a;
if(b[a])
{
printf("REPEAT\n");
}
else
{
b[a]=1;
pd(a);
}
}
return 0;
}
|
\(\qquad\!\!\)例题：
\(\qquad\!\!\)P1368
【模板】最小表示法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| #include<bits/stdc++.h>
#define in inline
#define re register
const int N=300010;
using namespace std;
int n,a[N];
in int qread()
{
int x=0,y=1;
int ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
{
y=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*y;
}
in void qwrite(re int x)
{
if(x<0)
{
putchar('-');
qwrite(-x);
}
else
{
if(x>9)
{
qwrite(x/10);
}
putchar(x%10+'0');
}
return ;
}
int main()
{
n=qread();
for(re int i=0;i<n;i++)
{
a[i]=qread();
}
int i=0,k=0,j=1;
while(i<n&&j<n&&k<n)
{
if(a[(i+k)%n]==a[(j+k)%n])
{
k++;
}
else
{
if(a[(i+k)%n]>a[(j+k)%n])
{
i=i+k+1;
}
else
{
j=j+k+1;
}
if(i==j)
{
i++;
}
k=0;
}
}
for(re int l=0;l<n;l++)
{
qwrite(a[(min(i,j)+l)%n]);
putchar(' ');
}
putchar('\n');
return 0;
}
|