The question :

Find the given string , The number of prefixes contained .

analysis :

Is to find the sum of the number of times all prefixes appear in the string , It can be used KMP The nature of , With j The end of the string contains the number of strings , Namely next[j] The ending string contains the number of prefixes plus it is itself a prefix ,dp[i] Said to i The number of prefixes to include at the end , be dp[i]=dp[next[i]]+1, Finally, sum it up .

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<11
#define All 1,N,1
#define read freopen("in.txt", "r", stdin)
#define N 200010
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
int dp[N],f[N],n;
char str[N];
void getnext(){
int i=,j=-;
f[]=-;
while(i<n){
if(j==-||str[i]==str[j])
{
i++;j++;
f[i]=j;
}
else j=f[j];
}
}
void solve(){
getnext();
//cout<<1<<endl;
memset(dp,,sizeof(dp));
int total=;
for(int i=;i<=n;++i){
dp[i]=(dp[f[i]]+)%mod;
total=(total+dp[i])%mod;
}
printf("%d\n",total);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",str);
solve();
}
return ;
}

hdu 3336 count the string(KMP+dp) More articles about

  1. HDU 3336 Count the string(KMP Of Next Array application +DP)

    Count the string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  2. POJ 3336 Count the string (KMP+DP, Good question )

    Refer to the connection : KMP+DP: http://www.cnblogs.com/yuelingzhi/archive/2011/08/03/2126346.html It's no use giving another one dp It's done :http:// ...

  3. 【HDU 3336】Count the string(KMP+DP)

    Problem Description It is well known that AekdyCoin is good at string problems as well as number the ...

  4. HDU 3336 - Count the string(KMP+ Recurrence )

    The question : Give a string , What is the total number of matches between all prefixes of the string and the string . This question is to use KMP Of next and DP To do it . next[i] What it means is when i When there is a character mismatch , The character position that the match pointer should trace back to . Subscript from 0 Start . ...

  5. hdu_3336: Count the string(KMP dp)

    Topic link The question : Find... In the given string , The number of all substrings that can be the same as a prefix Do this problem need to understand KMP In the algorithm next[] The meaning of arrays First, use an array nex[]( This is the same as mentioned in the previous blog next Obviously different ) The storage Prefix suffix is the longest ...

  6. hdu 3336 Count the string(next Array )

    The question : Count the number of times the prefix appears in the string Ideas :next Array , Recurrence #include<iostream> #include<stdio.h> #include<string.h&g ...

  7. hdu 3336:Count the string( data structure , strand ,KMP Algorithm )

    Count the string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  8. HDU 3336 Count the string(next Array application )

    Count the string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  9. hdu 3336 Count the string( Thinking can go by ,KMP)

    subject The following is not KMP Algorithm —— Here are kiki Tell me the way , What a great mind —— It's the clever use of markers , Mark all the places where the first one appears , Then look down from the mark over and over again . #include<stdio.h> # ...

Random recommendation

  1. java.lang.NoClassDefFoundError: [Lorg/hibernate/engine/FilterDefinition

    terms of settlement : The original :<bean id="sessionFactory"class="org.springframework.orm.hibernate3.annota ...

  2. VBS Create data table

    ' Create data table ' Parameters :strDBPath String type Database path ' Parameters :strTableName String type The name of the data table to be created ' Parameters :strColumnName String type Initialized field name , In fact, it can be regarded as ...

  3. Java Replace the text string in the entire folder with another string ( Can be used for project replication , Become another project )

    import org.junit.Test; import java.io.*; /** * User: HYY * Date: 13-8-18 * Time: Afternoon 8:11 * To change ...

  4. Struts2--Dynamic Result Dynamic result set

    ${r} : Represents a configuration file xml Can read action Of valuestack The content of 1. jsp Display file : <body> Dynamic results Make sure you don't forget to set... For the saved values of dynamic results set get Method &l ...

  5. Flex4 Skin customization

    Flex4 Skin customization [Skin Classes and Skin class ]           Blog classification : RIA-Flex4 special column FlexAdobeUPFlashUI First of all . About spark.skin.SparkSkin Class 1. ...

  6. JavaSE assert Assertive learning

    stay Java in ,assert The key word is from JAVA SE 1.4 Introduced , In order to avoid the old version of Java The code uses assert Keywords cause errors ,Java Assertion checking is not started by default when executing ( This is the time , All the assertions ...

  7. Python object-oriented programming ( On )

    Python Not only does it support process oriented programming , It also supports object-oriented programming . Engineering oriented is the process of analyzing and solving problems , And then use functions to implement these steps one by one , When using, you can call the functions one by one . Object oriented is to divide the problems to be solved into ...

  8. HTML Escape character Unicode and CSS Introduction to pseudo class

    CSS Pseudo classes are used to add special effects to some selectors . a:link {color: #FF0000} /* Links not visited */ a:visited {color: #00FF00} /* Links visited */ ...

  9. win32 A serial port programming,

    Translated from :ms-help://MS.MSDNQTR.v80.chs/MS.MSDN.v80/MS.WIN32COM.v10.en/dnfiles/html/msdn_serial.htm Articles written by foreigners , ...

  10. C++ Design patterns -- Parsing and Implementation

    Original address  http://c.chinaitlab.com/special/sjms/Index.html#a Navigation directory ※  Design pattern analysis and implementation -Factory Pattern ※  Design pattern analysis and implementation part 8 -C ...