E. Expenditure Reduction(用链式前向星存储下一个字符a在s中的位置)

Problem - E - Codeforces

题意:

菜单可以看作是一个只包含小写英文字母和数字的字符串S，俊平认为餐厅的核心特色是一个字符串F，它目前是S的一个子序列。Junpei要求你从S中找出满足要求的最短子串S′。

对于那些可能对子序列和子串的定义感到好奇的人，请考虑两个非空字符串A,B。

如果我们说A是B的子序列，我们可以找到一组|A|指数{ik}，其中1≤i1 如果我们说A是B的一个子串，我们可以从B中抹去一个（可能是空的）前缀和一个（可能是空的）后缀，得到A。
输入
第一行包含一个整数T（1≤T≤104），表示测试案例的数量。

对于每个测试用例，有一行包含两个字符串S,F(1≤|S|≤105,1≤|F|≤100)，用一个空格隔开。保证F是S的一个子序列，两个字符串都只包含小写英文字母（'a'到'z'）和数字（'0'到'9'）。

保证T案例的∑|S|不超过5×105。

输出
对于每个测试案例，在一行中打印一个字符串，表示包含F的S的最短子串。

如果有多个答案，打印其中任何一个。

题解:

用链式前向星存储下一个字符a在s中的位置

我们设nex[i][a]为在i这个位置要寻找字符a的话，我们最近应该跳到那个位置上。

#include<iostream>
#include<cstring>
using namespace std;
char s[100050],f[105];
int ne[100050][40];
int l,r;
int find(char c)
{
	if(c>='0'&&c<='9')
	{
		return c-'0';
	}
	else
	{
		return c - 'a'+10;
	}
}
void solve()
{
	cin >> s+1>>f+1;
	int n = strlen(s+1);
	int m = strlen(f+1);
	for(int i = 1;i <= n;i++)
	{
		for(int j = 0;j < 40;j++)
		ne[i][j] = -1;
	}
	for(int i = n-1;i >= 1;i--)
	{
		for(int j = 0;j < 40;j++)
		{
			ne[i][j] = ne[i+1][j];
		}
		ne[i][find(s[i+1])] = i + 1;
	}
	int mi = 1e9;
	l = 1,r = n;
	for(int i = 1,now;i <= n;i++)
	{
		if(s[i]!=f[1])
		{
			continue;
		}
		now = i;
		for(int j = 2;j <= m;j++)
		{
			if(ne[now][find(f[j])] == -1)
			return ;
			now = ne[now][find(f[j])];
		}
		if(mi>now-i+1)
		{
			r = now;
			l = i;
			mi = now - i+1;
		}
	}
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
		for(int i = l;i <= r;i++)
		cout<<s[i];
		cout<<"\n";
	}
}