input:
lebronjamesisgoat
goat
output:
13
1 4 4 4 4 4 3 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4
思路：
后知后觉突然有点理解了
先说说做法吧：
在字符串模式匹配中，这个做法明显区别于其他两个做法的点在于，BM算法每次都是从p的最后一个位置开始比较
而d数组(d数组用来记录需要往后移动多少位置)的计算相较KMP也比较简单
①如果这个字母没有在P串里出现或者这个字母为P串的最后一个，d[]=lp(即p的长度)
②如果这个字母出现在P串里且这个字母不为P串的最后一个
d[x]=lp-i-1(i为这个字母在p串中出现的位置的最大值)
原理：如果这个字母不在p串中出现，那么就没有必要和p传中的其他字母比较，直接后移lp就好。
如果出现在p串中，就先假设她和在p串中出现的位置的最大值的那个位置。
代码实现：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=111111;
int maxx=-0x3f3f3f3f;
char t[maxn],p[maxn];
int d[26];
int lt,lp;
void cald()
{
for(int i=0;i<26;i++) d[i]=lp;for(int i=0;i<lp-1;i++) d[p[i]-'a']=lp-i-1;
}
int bmmatch()
{
int i=lp-1,j,k;do{
j=lp-1;k=i;while(j>=0&&p[j]==t[k]){
j--;k--;}if(j<0) return i-lp+1;i=i+d[t[i]-'a'];}while (i<lt);return -1;
}int main()
{
cin>>t>>p;lt=strlen(t);lp=strlen(p);cald();int ans=bmmatch();cout<<ans<<endl;for(int i=0;i<25;i++) cout<<d[i]<<" ";cout<<d[25];cout<<endl;return 0;
}