|
从网上搜题解都是后缀自动机
然而本蒟蒻不会后缀自动机，只好乱搞
第一个问题对B建trie跑就好
第二个问题可以枚举子串
第三个问题可在B串的trie上dfs，具体见代码
第四个问题用f[i][j]表示在A中前i个字符选j个（一定包含i）在B中匹配到的最小位置，裸dp是O(n^3)，加一些优化可以到O(26*n^2)
另外bzoj上只给了256M内存，我如果trie和用于dp优化的数组同时开就会MLE。。于是只好共用了一个数组。。。
#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 2003
#define MAXT 2003000
char a[MAXN], b[MAXN];
int n, m;
int trie[MAXT][26], cntr = 1;
bool end[MAXT];
void addstring(const char *s)
{
int p = 0;
for (const char *i = s; *i; ++i)
{
if (trie[p][*i - 'a'] == -1)
trie[p][*i - 'a'] = cntr++;
p = trie[p][*i - 'a'];
end[p] = true;
}
}
int find1(const char *s)
{
int p = 0, f = 1;
for (const char *i = s; *i; ++i, ++f)
{
if (trie[p][*i - 'a'] == -1)
return f;
p = trie[p][*i - 'a'];
}
return INT_MAX;
}
void work1()
{
int ans = INT_MAX;
for (int i = 0; i < n; ++i)
ans = min(ans, find1(a + i));
if (ans == INT_MAX)
puts("-1");
else
printf("%d\n", ans);
}
int next[MAXN][26], first[26];
void work2()
{
for (int i = 0; i < 26; ++i)
next[m - 1][i] = m;
for (int i = m - 2; i >= 0; --i)
{
memcpy(next[i], next[i + 1], sizeof(int) * 26);
next[i][b[i + 1] - 'a'] = i + 1;
}
for (int i = 0; i < 26; ++i)
first[i] = m;
for (int i = 0; i < m; ++i)
if (first[b[i] - 'a'] == m)
first[b[i] - 'a'] = i;
int ans = INT_MAX;
for (int i = 0; i < n; ++i)
{
if (first[a[i] - 'a'] == m)
ans = 1;
int pos = first[a[i] - 'a'];
for (int j = i + 1; j < n; ++j)
if (next[pos][a[j] - 'a'] == m)
{
ans = min(ans, j - i + 1);
break;
}
else
pos = next[pos][a[j] - 'a'];
}
if (ans == INT_MAX)
puts("-1");
else
printf("%d\n", ans);
}
int dfs3(int x, int pos, int cnt)
{
for (int i = 0; i < 26; ++i)
if (trie[x][i] == -1 && (pos == -1 ? first[i] : next[pos][i]) != n)
return cnt + 1;
int ans = INT_MAX;
for (int i = 0; i < 26; ++i)
{
int tmp = pos == -1 ? first[i] : next[pos][i];
if (tmp != n)
ans = min(ans, dfs3(trie[x][i], tmp, cnt + 1));
}
return ans;
}
void work3()
{
for (int i = 0; i < 26; ++i)
next[n - 1][i] = n;
for (int i = n - 2; i >= 0; --i)
{
memcpy(next[i], next[i + 1], sizeof(int) * 26);
next[i][a[i + 1] - 'a'] = i + 1;
}
for (int i = 0; i < 26; ++i)
first[i] = n;
for (int i = 0; i < n; ++i)
if (first[a[i] - 'a'] == n)
first[a[i] - 'a'] = i;
int ans = dfs3(0, -1, 0);
if (ans == INT_MAX)
puts("-1");
else
printf("%d\n", ans);
}
inline int getpos(int x, int y)
{
return (x + 4) * (x + 1) / 2 - (x + 2 - y);
}
void work4()
{
static int f[MAXN][MAXN];
/* 0 - 2 1 - 3 2 - 4 */
//static short g[MAXN][MAXN][26];
//g[x][y] trie[(x+4)(x+1)/2-(x+2-y)]
memset(trie, 0, sizeof(trie));
for (int i = 0; i < 26; ++i)
next[m - 1][i] = m;
for (int i = m - 2; i >= 0; --i)
{
memcpy(next[i], next[i + 1], sizeof(int) * 26);
next[i][b[i + 1] - 'a'] = i + 1;
}
for (int i = 0; i < 26; ++i)
first[i] = m;
for (int i = 0; i < m; ++i)
if (first[b[i] - 'a'] == m)
first[b[i] - 'a'] = i;
for (int i = 0; i < n; ++i)
for (int j = 0; j <= n; ++j)
f[i][j] = m;
int ans = INT_MAX;
for (int i = 0; i < n; ++i)
{
f[i][0] = -1;
f[i][1] = first[a[i] - 'a'];
if (f[i][1] == m)
ans = min(ans, 1);
for (int j = 2; j <= i + 1; ++j)
{
//f[i][j] = g[i - 1][j - 1][a[i] - 'a'];
f[i][j] = trie[getpos(i - 1, j - 1)][a[i] - 'a'];
if (f[i][j] == m)
ans = min(ans, j);
}
for (int j = 1; j <= i + 1; ++j)
for (int k = 0; k < 26; ++k)
//g[i][j][k] = max(i ? g[i - 1][j][k] : 0, next[f[i][j]][k]);
trie[getpos(i, j)][k] = max(i ? trie[getpos(i - 1, j)][k] : 0, next[f[i][j]][k]);
}
if (ans == INT_MAX)
puts("-1");
else
printf("%d\n", ans);
}
int main()
{
scanf("%s%s", a, b);
memset(trie, 0xff, sizeof(trie));
n = strlen(a), m = strlen(b);
for (int i = 0; i < m; ++i)
addstring(b + i);
work1();
work2();
work3();
work4();
return 0;
}
| 
转播
