codeforces 113 B Petr# (一道用了函数就会的题)

strncmp函数是指定比较size个字符。也就是说，如果字符串s1与s2的前size个字符相同，函数返回值为0。此函数功能即比较 字符串str1和str2的前maxlen个字符。如果前maxlen 字节完全相等，返回值就=0；在前maxlen字节比较过程中，如果出现str1[n]与str2[n]不等，则依次比较str1和str2的前n位，设i(i<n)为两字符串首次的不同位，则返回（str1[i]-str2[i]）。

用了这个神函数再加上一个很水的Trie树 ，第一次发现用数组的Trie树

就是看字符串是福曾经存在，因为Trie的查找复杂度有点低，如果用map的话一个是map 的查找复杂度有点高，其实用字符串hash一样的，so   我用了trie   ，

/*************************************************************************> File Name: x.cpp> Author: wuhulala> Mail: xueaohui_com@163.com> Created Time: 2015/1/4 21:07:12************************************************************************/#include<iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;#define N 2222
char s[3000];
char b[3000],e[3000];
int ans;
int vis[N*N/2][26];
int len;
int sta1[3000];
int sta2[3000];
int lenb,lene;void serach(int x){int cur =0;for(int i=x;s[i];i++){if(!vis[cur][s[i]-'a']){if(sta2[i]&&i>=lenb+x-1&&i>=x-1+lene) ans++;vis[cur][s[i]-'a']=len++;}cur=vis[cur][s[i]-'a'];}
}int main(){scanf("%s%s%s",s,b,e);lenb=strlen(b);lene=strlen(e);for(int i=0;s[i];i++){if(!strncmp(s+i,b,lenb)) sta1[i]=1;if(!strncmp(s+i,e,lene)) sta2[i+le-1]=1;}ans=0;len = 1;for(int i=0;s[i];i++)if(sta1[i])serach(i);cout<<ans<<endl;
}