(UVA) 11576 - Scrolling Sign

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=24&problem=2623

applicant of KMP

#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 106;

int f[MAX_N];

void build(string s) {
    int len=s.size();
    int pos=-1;
    f[0]=-1;
    for (int i=1;len>i;i++) {
        while (pos != -1 && s[pos+1] != s[i]) {
            pos = f[pos];
        }
        if (s[pos+1] == s[i]) pos++;
        f[i] = pos;
    }
}

int match(string a,string b) {
    int lena=a.size(),lenb=b.size();
    int mx=-1;
    int pos=-1;
    for (int i=0;lena > i;i++) {
        while (pos != -1 && a[i] != b[pos+1]) {
            pos = f[pos];
        }
        if (a[i] == b[pos+1]) pos++;
        if (i==lena-1) return pos;
        if (pos == lenb - 1) {
            mx = pos;
            pos = f[pos];
        }
        else {
            mx = max(mx,pos);
        }
    }
    return mx;
}

string s[MAX_N];

int main () {
    int T;
    cin >> T;
    while (T--) {
        int a,b;
        cin >> a >> b;
        int ans=0;
        for (int x=0;b>x;x++) {
            cin >> s[x];
            ans += s[x].size();
            if (x==0) continue;
            build(s[x]);
            //cout <<"match = "<<match(s[x-1],s[x])<<endl;
            ans -= match(s[x-1],s[x]);
            ans -= 1;
        }
        printf("%d\n",ans);
    }
}