KFC Crazy Thursday---马拉车/二分+字符串哈希

马拉车

#include 
#include 
#include 
using namespace std;
const int N = 1e6 + 10;

int n;
char a[N], b[N];
int p[N];
int res1, res2, res3;
void init()
{
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = 0;
    n = k;
}

void manacher()
{
    int mr = 0, mid;
    for (int i = 1; i < n; i ++ )
    {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
        if (i + p[i] > mr)
        {
            mr = i + p[i];
            mid = i;
        }
        
        for(int j = i; j <= i + p[i] - 1; j ++)
        {
            res1 += b[j] == 'k';
            res2 += b[j] == 'f';
            res3 += b[j] == 'c';
        }    
    } 
}

int main()
{
    cin >> n;
    scanf("%s", a);

    init();
    manacher();

    cout << res1 << ' ' << res2 << ' ' << res3 << '\n';
}

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

二分 + 字符串哈希

#include 
#include 
#include 

using namespace std;
#define int long long
const int N = 1000010;
int n;
char s[N], str[N];
int sum[N][4];
int res1, res2, res3;
unsigned long long p[N], L[N], R[N];

bool check(int x, int len)
{
	return L[x] - L[x - len] * p[len] == R[x] - R[x + len] * p[len];
}

signed main()
{
	int k; cin >> k;
	cin >> str + 1; 
    for (int i = 1; i <= k; i ++) 
    {
		s[++n] = '*';
		s[++n] = str[i];
	}
	s[++n] = '*';
    p[0] = 1;
    for(int i = 1; i <= n; i ++)
	{
		p[i] = p[i - 1] * 131;
		L[i] = L[i - 1] * 131 + s[i] - 'a';
		sum[i][1] = sum[i-1][1] + (s[i] == 'k');
		sum[i][2] = sum[i-1][2] + (s[i] == 'f');
		sum[i][3] = sum[i-1][3] + (s[i] == 'c');
	}
	for(int i = n; i >= 1; i --)
		R[i] = R[i + 1] * 131 + s[i] - 'a';
	for(int i = 1; i <= n; i ++)
	{
		int l = 1, r = min(i, n - i + 1);
		while(l < r)
		{
			int mid = l + r + 1 >> 1;
			if(check(i, mid)) l = mid;
			else r = mid - 1;
		}
		res1 += sum[i + r - 1][1] - sum[i - 1][1];
		res2 += sum[i + r - 1][2] - sum[i - 1][2];
		res3 += sum[i + r - 1][3] - sum[i - 1][3];
	}
	cout << res1 << " " << res2 << " " << res3 << '\n';
}
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