BZOJ 1009 HNOI2008 GT考試 KMP算法+矩陣乘法
題目大意：給定長度為m的數字串s，求不包含子串s的長度為n的數字串的數量
n<=10^9 光看這個O(n)就是掛
我們不考慮這個 令f[i][j]為長度為i的數字串中最後j位與s中的前j位匹配的方案數
比如當s為12312時 f[i][3]表示長度為i，以123結尾且不包含子串”12312“的方案數
a[x][y]為f[i-1][x]轉移至f[i][y]的方案數
換句話說(可能描述不清楚) a[x][y]為s的長度為x的前綴加上一個數字後 後綴可以與最長長度為y的前綴匹配 這個數字可以有多少種
比如說12312 這個數字串生成的a數組為(數組從0開始)：
9 1 0 0 0 0
8 1 1 0 0 0
8 1 0 1 0 0
9 0 0 0 1 0
8 1 0 0 0 1
a[2][1]=1 表示長度為2的前綴加上一個'1'之後最多與長度為1的前綴匹配
a[4][0]=8 表示長度為4的前綴加上'1''2'以外的數就變成了長度為0的前綴
但是a[x][5]表示完全匹配，不滿足要求的題意，所以我們矩陣乘法時不考慮這一列
我們發現f[i-1]乘上這個矩陣就變成了f[i] 這個矩陣怎麼求呢？KMP算法，對於每個長度的前綴枚舉下一個字符進行轉移 具體寫法詳見代碼
f初值是f[0][0]=1,f[0][x]=0 (x>0)
於是最後我們只需要取答案矩陣的第一行即可
去網上找了一堆題解才看懂0.0 這裡寫的稍微詳細一點吧
#include
#include
#include
#include
using namespace std;
struct matrix{
int xx[22][22];
int* operator [] (int x)
{
return xx[x];
}
}a,b;
int n,m,p,ans;
char s[100];
int next[100];
void operator *= (matrix &x,matrix &y)
{
int i,j,k;
matrix z;
memset(&z,0,sizeof z);
for(i=0;i>=1;
}
}
int main()
{
int i;
cin>>n>>m>>p;
scanf("%s",s+1);
KMP();
for(i=0;i
