一个网站项目的价格表,dz论坛seo,wordpress防cc代码,建设部网站公告注册成功P4173 残缺的字符串
题意#xff1a;
有A#xff0c;B两个串#xff0c;每个串都有通配符#xff0c;问A为模板串#xff0c;对于 B 的每一个位置 i#xff0c;从这个位置开始连续 m 个字符形成的子串是否可能与 A 串完全匹配#xff1f;
题解#xff1a;
我们定义…P4173 残缺的字符串
题意
有AB两个串每个串都有通配符问A为模板串对于 B 的每一个位置 i从这个位置开始连续 m 个字符形成的子串是否可能与 A 串完全匹配
题解
我们定义两个字符串ST的距离为 dis(S,T)∑i1m−1(Si−Ti)2∗Si∗Ti\sum_{i1}^{m-1}(S_{i}-T_{i})^2*S_{i}*T_{i}∑i1m−1(Si−Ti)2∗Si∗Ti 当T中以i结尾的串与S能匹配的条件为 dis(S,T[i−m1,i])0dis(S,T[i-m1,i])0dis(S,T[i−m1,i])0 fi∑j0m−1(Sj−Ti−j)2∗Sj∗Ti−j∑j0m−1Sj3∗Ti−j−2∗∑j0m−1Sj2Ti−j2∑j0m−1Sj∗Ti−j3f_{i}\sum_{j0}^{m-1}(S_{j}-T_{i-j})^2*S_{j}*T_{i-j}\sum_{j0}^{m-1}S_{j}^{3}*T_{i-j}-2*\sum_{j0}^{m-1}S_{j}^{2}T_{i-j}^{2}\sum_{j0}^{m-1}S_{j}*T_{i-j}^{3}fi∑j0m−1(Sj−Ti−j)2∗Sj∗Ti−j∑j0m−1Sj3∗Ti−j−2∗∑j0m−1Sj2Ti−j2∑j0m−1Sj∗Ti−j3 我的板子 人傻了 这里贴的是别人的板子开氧过了不开80
代码
// Problem: P4173 残缺的字符串
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4173
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Data:2021-08-24 00:29:28
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
#define MAXN 2000005
#define reg register
#define inl inline
#define db double
#define eps 1e-6
using namespace std;
const int Mod 998244353;
const db Pi acos(-1.0);
struct Complex
{db x, y;friend Complex operator(const Complex a, const Complex b){return ((Complex){a.x b.x, a.y b.y});}friend Complex operator-(const Complex a, const Complex b){return ((Complex){a.x - b.x, a.y - b.y});}friend Complex operator*(const Complex a, const Complex b){return ((Complex){a.x * b.x - a.y * b.y, a.x * b.y a.y * b.x});}friend Complex operator*(const Complex a, const db val){return ((Complex){a.x * val, a.y * val});}
} f[MAXN], g[MAXN], p[MAXN];
int n, m, lim 1, maxn, rev[MAXN], a[MAXN], b[MAXN];
char S[MAXN], T[MAXN];
bool used[MAXN];
vectorint v;
inl void FFT(reg Complex* A, reg int opt)
{for (reg int i 0; i lim; i)if (i rev[i])swap(A[i], A[rev[i]]);for (reg int mid 1; mid lim; mid 1) {reg Complex Wn ((Complex){cos(Pi / (db)mid), (db)opt * sin(Pi / (db)mid)});for (reg int j 0; j lim; j (mid 1)) {reg Complex W ((Complex){1, 0});for (reg int k 0; k mid; k, W W * Wn) {reg Complex x A[j k], y W * A[j k mid];A[j k] x y;A[j k mid] x - y;}}}
}
int main()
{scanf(%d %d, m, n);scanf(%s, T 1);scanf(%s, S 1);for (reg int i 1; i m; i)if (T[i] ! *)a[i - 1] T[i] - a 1;for (reg int i 1; i n; i)if (S[i] ! *)b[i - 1] S[i] - a 1;while (lim (n m)) {lim 1;maxn;}for (reg int i 0; i lim; i)rev[i] ((rev[i 1] 1) | ((i 1) maxn - 1));reverse(a, a m);for (reg int i 0; i m; i)f[i] ((Complex){a[i] * a[i] * a[i], 0});for (reg int i 0; i n; i)g[i] ((Complex){b[i], 0});FFT(f, 1);FFT(g, 1);for (reg int i 0; i lim; i)p[i] p[i] f[i] * g[i];for (reg int i 0; i lim; i)f[i] g[i] ((Complex){0, 0});for (reg int i 0; i m; i)f[i] ((Complex){a[i] * a[i], 0});for (reg int i 0; i n; i)g[i] ((Complex){b[i] * b[i], 0});FFT(f, 1);FFT(g, 1);for (reg int i 0; i lim; i)p[i] p[i] - f[i] * g[i] * 2.0;for (reg int i 0; i lim; i)f[i] g[i] ((Complex){0, 0});for (reg int i 0; i m; i)f[i] ((Complex){a[i], 0});for (reg int i 0; i n; i)g[i] ((Complex){b[i] * b[i] * b[i], 0});FFT(f, 1);FFT(g, 1);for (reg int i 0; i lim; i)p[i] p[i] f[i] * g[i];FFT(p, -1);for (reg int i m - 1; i n; i)if (!(int)(p[i].x / (db)lim 0.5))v.push_back(i - m 2);reg int Ans v.size();printf(%d\n, Ans);for (reg int i 0; i Ans; i)printf(%d , v[i]);return 0;
}
