Training summary report

    First of all, I'll fill in a water problem that stuck me for a long time this afternoon ：

     Xinjiang University ACM-ICPC Programming competition may （ Synchronized competition ）Red Rover

   One of our older Mars Rovers has nearly completed its tour of duty and is awaiting instructions
for one last mission to explore the Martian surface. The survey team has picked a route and has
entrusted you with the job of transmitting the final set of instructions to the rover. This route
is simply a sequence of moves in the cardinal directions: North, South, East, and West. These
instructions can be sent using a string of corresponding characters: N, S, E, and W. However,
receiving the signal drains the rover’s power supply, which is already dangerously low. Fortunately,
the rover’s creators built in the ability for you to optionally define a single “macro" that can be used
if the route has a lot of repetition. More concretely, to send a message with a macro, two strings are
sent. The first is over the characters {N,S,E,W,M} and the second is over {N,S,E,W}. The first
string represents a sequence of moves and calls to a macro (M), while the second string determines
what the macro expands out to. For example:
WNMWMME
EEN
is an encoding of
WNEENWEENEENE
Notice that the version with macros requires only 10 characters, whereas the original requires 13.
Given a route, determine the minimum number of characters needed to transmit it to the rover.
Input
Input consists of a single line containing a string made up of the letters N, S, E, and W representing
the route to transmit to the rover. The maximum length of the string is 100.
Input
Display the minimum number of characters needed to encode the route.
Sample Input 1 Sample Output 1
WNEENWEENEENE 10
Sample Input 2 Sample Output 2
NSEW 4
ECNA 2016 Problem E: Red Rover 9
Sample Input 3 Sample Output 3
EEEEEEEEE 6

    The question ： Give you a string s, Let you find a substring s1, hold s All that has appeared in s1 Replace them with characters M, Ask if you can make the string s How short is it , Output the shortest length  

   Ideas ： First enumerate the substrings in each original string , use kmp Find the number of non overlapping substrings in the original string , Keep maintaining cnt, Finally find the minimum , That is to say kmp+ violence

  problem ： This question really stuck me for a long time , The sample is always over 90% , I've been trying to find out if there is any missing boundary in my solution ... Finally found my kmp In the algorithm getfail（） The function did not call ！！！... There are so many sets of examples ... Be angry

   AC Code ：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=111;
int f[maxn];
void getFail(char *P,int m){
    memset(f,0,sizeof(f));
    //int m =strlen(P);
    //f[0]=f[1]=0;
    for(int i=1;i<m;i++)
    {
        int j=f[i];
        while(j && P[i]!=P[j]) j=f[j];
        f[i+1] = (P[i]==P[j])?j+1:0;
    }
}
int kmp(char *T,char *P,int m)
{
    
    int cnt=0;
    int n=strlen(T);
    //int m=strlen(P);
    int j=0;
    for(int i=0;i<n;i++)
    {
        while(j && T[i]!=P[j]) j=f[j];
        if(T[i]==P[j]) j++;
        if(j==m)
        {
            cnt++;
            j=0;//kmp No overlapping substring core found 
        }
    }
    return cnt;
}
 
int main()
{
    char s[maxn];
    cin>>s;
    int len =strlen(s);
    int sum= len;
    for(int i=0;i<len;i++)
    {
        for(int j=i+1;j<len;j++)
        {
            int c=0;
            char tmp[105];
            for(int k=i;k<=j;k++)
            {
                tmp[c]=s[k];
                c++;
            }
             getFail(tmp,c);
            int tt=kmp(s,tmp,c);
            int t1=c;
            sum=min(sum,len-tt*t1+tt+t1);
        }
    }
    printf("%d\n",sum);
    return 0;
}

      After this afternoon's game , The training before the provincial competition has come to an end for the time being , Since the May Day holiday, I have formed a team to play a practice match every day , In theory, the strength of our team is not weak , But the play is not very stable , The knowledge of ideas and algorithms is not bad , But sometimes it's always stuck by some basic mistakes , There are always ideas right , But it is AC No. , When you make up the last question, you will find that there are always some mistakes that should not appear , For example, the array is not empty , The function did not call ,bool The use of arrays optimizes time and space, and so on , These problems have appeared in these team games .

    I discussed with my teammates about the situation of the game these days , Divide the responsibility of each person again , And question making strategies ： At the beginning, three people pass the simple questions as quickly as possible , Then two people do the slightly difficult problem together , Also cross check the code , Prevent fundamental errors .

      And through these games , I found that there are many problems in finding rules , It seems that we should pay attention to the law , You can't think of it simply , You should first calculate your algorithm complexity , Then determine your own practice according to the time limit of the topic .