string

string

1.string 字符串回溯

B-小红的01连续段_第20届纪念款-牛客周赛 Round 20 (nowcoder.com)

#include<iostream>

using namespace std;

void solve()
{
	string s;cin >> s;int ans = 0;
	for(int i = 0;i < s.size();)
	{
		int j = i, flag = 0;
		for(;j < s.size();j ++)
		{
			if(!flag && s[j] != '?') flag = s[j];
			if(!flag || s[j] == '?' || s[j] == flag) continue;
			else break;
		}
		ans = max(j - i, ans);
		while(s[j - 1] == '?' && j != s.size()) j --;
		i = j;
	}
	cout << ans << endl;
}

int main()
{
	solve();
	return 0;
}

2.tire树的思路和代码

tire树的思路 使用idx来完成string是否相等的判断和储存，对应的每一个新的string字符串都可以使用idx来存储，并且每一个新的字符串的idx值不相同，所以在查找和插入的函数内的p来得到每一个不同的值，存入cnt数组中

#include<iostream>

using namespace std;
const int N = 1e5 + 10;
int tire[N][27], cnt[N], idx;


void insert(string s)
{
	int p = 0;
	for(int i = 0;i < s.size();i ++)
	{	
		int u = s[i] - 'a';
		if(!tire[p][u]) tire[p][u] = idx ++;
		p = tire[p][u];
	}
	cnt[p] ++;
}

int find(string s)
{
	int p = 0;
	for(int i = 0;i < s.size();i ++)
	{
		int u = s[i] - 'a';
		if(tire[p][u]) p = tire[p][u];
		else return 0;
	}
	return cnt[p];
}

void solve()
{
	int n;cin >> n;
	while(n --)
	{
		char op;string s;
		cin >> op >> s;
		if(op == 'I')insert(s);
		else	cout << find(s) << endl;
	}
}

int main()
{
	solve();
	return 0;
}

3.字符串哈希

#include<iostream>

using namespace std;
const int N = 1e5 + 10, P = 131;
typedef unsigned long long ull;
ull cnt[N], f[N];

ull get(int l,int r)
{
	return cnt[r] - cnt[l - 1] * f[r - l + 1];
}

void solve()
{
	int n, k;cin >> n >> k;
	string s;cin >> s;s = '3' + s;
	f[0] = 1;
	for(int i = 1;i <= n;i ++)
	{
		cnt[i] = s[i] + cnt[i - 1] * P;
		f[i] = f[i - 1] * P;
	}	
	
	while(k --)
	{
		int l1, r1, l2, r2;cin >> l1 >> r1 >> l2 >> r2;
		if(get(l1,r1) == get(l2,r2)) puts("Yes");
		else puts("No");
	}

}

int main()
{
	solve();
	return 0;
}