Today I was trying to solve the problem CF R1600 — Camp Schedule. I realized that I will need the longest prefix of a string which is also a suffix of that string. I searched it on google and found that it is called 'Prefix Function'. I tried to understand this concept from the CP Algorithms article, but I am too dumb to understand it.

Though I got the code from there what I needed, I can't understand how it works. Can anyone please help me to understand this concept? (with some examples?)

// everything 0-indexed
// pi[i] = 0 -> empty string matched
// pi[i] = j -> prefix s[0..(j)] matched
int prefixFunction(const string& s){
    
    int n = sz(s);
    
    vector<int> pi(n);
    
    for(int i = 1; i < n; i++){
        
        int j = pi[i - 1];
        
        while(j > 0 && s[j] != s[i]) j = pi[j - 1]; // This part is hard to understand for me.
        if(s[j] == s[i]) j++;
        pi[i] = j;
    }
    return pi[n - 1];
}

Note: I am very new to this type of algorithms.

As I am very new to dynamic programming I am facing many problems in understanding the states of the DP. Here is a problem which I have tried to solve by iterative method but failed. Can anyone please help me with this problem by giving me a bit description on how to understand the states of this type of problems?

Problem Statement: Find a sub-sequence $$$(a_{b1}, a_{b2}, a_{b3},\dots)$$$ of array $$$a$$$ of size $$$n(n < 1001)$$$ to maximize the following expression: $$$1*a_{b1} + 2*a_{b2} + 3*a_{b3} + \dots$$$. Print the maximum value of the expression.