P4173 殘缺的字符串

題意：

有A，B兩個串，每個串都有通配符，問A為模板串，對于 B 的每一個位置 i，從這個位置開始連續 m 個字符形成的子串是否可能與 A 串完全匹配？

題解：

我們定義兩個字符串S，T的距離為：
dis(S,T)=${\sum }_{i=1}^{m?1}(S_i?T_i{)}^2?S_i?T_i$
當T中以i結尾的串與S能匹配的條件為：
$dis(S,T[i?m+1,i])=0$
$f_i={\sum }_{j=0}^{m?1}(S_j?T_{i?j}{)}^2?S_j?T_{i?j}={\sum }_{j=0}^{m?1}{S}_j^3?T_{i?j}?2?{\sum }_{j=0}^{m?1}{S}_j^2{T}_{i?j}^2+{\sum }_{j=0}^{m?1}{S}_j?T_{i?j}^3$
我的板子
人傻了

這里貼的是別人的板子，開氧過了，不開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 pair<int, 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]; vector<int> 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; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P4173 残缺的字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。