字符串习题

给定两个字符串S和T
你每次可以在S的某个字符c后面添加一个字符d，要保证c!=d
问有没有可能把S变成T
1<=|S|<=|T|<=1e5 

首先S必须要是T的子序列，且S1=T1
因为字符不同的限制，所以S开头连续相同的字符数要不小于T开头的连续相同的字符数
如果满足以上条件，那么一定可以得到T
时间复杂度O（n） 
 

#include<iostream>
#include<cstdio>
#include<cstring> 
 
int solve()
{
	int i,j;
	int l1=strlen(s);
	int l2=strlen(t);
	for (i=1;i<l2;i++)
	 if (t[i]!=t[0]) break;//找到t串的第一个不连续的位置 
    for (j=0;j<i;j++)    //看s的钱i个子串是否连续 
     if (s[j]!=t[0]) return 0;   
     
    for (;j<l1;){
    	for (;i<l2;i++)       //找到下一个和s相等的地方 
    	  if (t[i]==s[j]) break;
	    if (i==l2) return 0;
	    i++;j++;
	}
	return 1;
}
 


int main(){
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%s%s",s,t);
		if (solve())
		   printf("Yes\n");
		else printf("No\n");
	}
	return 0;
} 



给定n个串，有m次询问，每次询问给定串a，b，问n个串中有多少个表示为axb，其中x为任意字符串
s<=1e6
条件等价于前缀为a，后缀为b，且长度>=|a|+|b|的个数

不考虑长度的情况下，将正串和反串分别按字典序编号，一个询问对应了编号的一个区间，用字典树或排序+二分+hash求出区间，然后主席树求答案。
然后考虑剪掉长度不足的。直接枚举长度就可以确定出字符串了。
时间复杂度O（slogs）


给定一个长度为n的串s，一个长度为m的串t。
有k次询问，每次给定l,r,在[l,r]中随机一个整数i，整数j，问t在s[1..i]+s[j..n]中的期望出现次数。
n,k<=1e5,m<=1e2.

分别考虑t在s[1..i]和s[j...n]中的期望以及跨越中间的期望。
前者只要找出t在s中的出现位置然后求前/后缀和即可。
后者考虑枚举在s[1..i]中的长度k，求出t[1..k]和t[k+1..m]的出现位置然后求前/后缀和即可。
时间复杂度O((n+k)m)


选一颗n个点的树，每条边有一个小写字母
对于两个
迷失的字符串不同的点u,v，将u到v路径上沿途经过的边上的字符依次写下来，得到一个字符串。
对于一个字符串，如果存在这样一个点对(u,v),使得它们路径上的字符串与其完全匹配，那么我们就称这个字符串属于这颗树。
有m个字符串，判断每一个字符串是否属于这棵树。
n,m<=3e4,字符串总长s<=3e5

对单独一个串可以dp，f[w][i]表示走到w这条边(边分为两个方向)，是否能匹配到第i个字符。
将所有串的第二维压到一起，用bitset优化，转移时左移一位，与上这条边的字符c对应的数组u[c],再或上v[c]。 
u[c][i]=1当且仅当第i个位置对应的字符为c
v[c][i]=1当且仅当第i个位置对应的字符为c且它是某个串的第一个字符 
时间复杂度O（ns/32） 

Podzial naszyjnika

给定一串长度为n的项链，每颗珠子是k种颜色之一。
切两刀，把项链断成两条链。要求每种颜色的珠子只能出现再其中一条链中。
求方案数（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

2<=k<=n<=1e6