String Similarity

                            Solution in C :

In    C++  :








#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <sstream>
#include <map>
#include <set>
#include <numeric>
#include <memory.h>
#include <cstdio>
#include <assert.h>
#include <numeric>

using namespace std;

#define pb push_back
#define INF 1011111111
#define FOR(i,a,b) for (int _n(b), i(a); i < _n; i++)
#define rep(i,n) FOR(i,0,n)
#define ford(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define CL(a,v) memset((a),(v),sizeof(a))
#define mp make_pair
#define X first
#define Y second
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))

typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> pii;

vector<ll> z_func(const string &s)
{
    int n = s.size();
    vector<ll> z(n,0);
    int l = 0,r = 0;

    FOR(i,1,n)
    {
        if(i <= r)
            z[i] = min(z[i-l], (ll)r-i+1);

        while(i+z[i] < n && s[i+z[i]] == s[z[i]]) z[i] ++;

        if(i+z[i]-1 > r)
            r = i+z[i]-1, l = i;
    }

    return z;
}

int main()
{
	#ifndef ONLINE_JUDGE
        //freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
	#endif

    int T;
    cin >> T;

    while(T--)
    {
        string s;
        cin >> s;

        vector<ll> z = z_func(s);

        cout << 1LL*s.size() + accumulate(all(z), 0LL) << endl;
    }

	return 0;
}









In   Java   :







import java.util.Scanner;


public class Solution {

	private String[] strArray;
	
	public boolean read(){
		
		Scanner sc = new Scanner(System.in);
		int n = Integer.valueOf(sc.nextLine());
		strArray = new String[n];
		int i = 0;
		while(i < n){
			
			strArray[i++] = sc.nextLine();
		}
		
		return true;
	}
	
	public void solve(){
		
    	for(String s : strArray){
	    	int len = s.length();
	    	int sum = len;
	    	for(int i=1; i<len;i++){
	    		int count = 0;
	    		for(int j=0,k=i; j<len && k<len; j++,k++){
	    			  if(s.charAt(k) == s.charAt(j)){
	    				  count++;
	    			  }else{
	    				  break;
	    			  }
	    		}
	    		sum = sum + count;
	    	}
	    	System.out.println(sum);
    	}
    	
	}
	public void solveIt(){
		
    	for(String s : strArray){
	    	int len = s.length();
	    	long sum = len;
	    	char ch = s.charAt(0);
	    	int pos = s.indexOf(ch, 1);	    	
	    	while(pos != -1){
	    		long count = 1;
	    		for(int j=1,k=pos+1; j<len && k<len; j++,k++){
	    			  if(s.charAt(k) == s.charAt(j)){
	    				  count++;
	    			  }else{
	    				  break;
	    			  }
	    		}
	    		sum = sum + count;
	    		pos = s.indexOf(ch, pos+1);
	    	}
	    	System.out.println(sum);
    	}
    	
	}

	public void solveZ(){
		
    	for(String s : strArray){
	    	int len = s.length();
	    	long sum = len;
	    	int[] z = new int[len];
	    	int l=0,r=0;
	    	for(int k=1;k<len;k++){
	    		int j;
	    		if(k < r){
	    			j = ((r-k) < z[k-l] )? (r-k) : z[k-l];
	    		}else{
	    			j = 0;
	    		} 
	    		while(k+j < len){
	    			
	    			if(s.charAt(k+j) == s.charAt(j)){
	    				j++;
	    			}else{
	    				break;
	    			}
	    		}
	    		z[k] = j;
	    		sum = sum + z[k];
	    		if(k+j > r){
	    			l = k;
	    			r= k+j;
	    		}

	    	}
	    	System.out.println(sum);
    	}
    	
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Solution s = new Solution();
		if(s.read()){
			s.solveZ();
		}
		
	}

}








In    C  :







#include <stdio.h>
#include <string.h>

#define N 200000
char str[N];
int pre[N];
int len[N];

int main() {
	int tc;
	scanf("%d", &tc);
	while (tc --) {
		memset(pre, -1 , sizeof(pre));
		memset(len, 0, sizeof(len));
		scanf("%s", str);
		int n = strlen(str);
		long long sum = 0;
		int k = -1;
		int pos = 0;
		while (pos + 1 < n) {
			if (str[k + 1] == str[pos + 1]) {
				k++; pos++;
				pre[pos] = k;
				len[pos - k] = k + 1;
			} else if (k == -1) {
				pos++;
			} else {
				k = pre[k];
				len[pos - k] = k + 1;
			}
		}
		while (k > 0) {
			k = pre[k];
			len[pos - k] = k + 1;
		}
		len[0] = n;
		for (int i = 0; i < n; i++) {
			sum += len[i];
		}

		for (int i = 0; i < n; i++) {
			if (len[i] == 0) {
				for (int j = 0; i + j < n; j++) {
					if (str[j] == str[i+j]) {
						sum++;
					} else {
						break;
					}
				}
			}
		}
		printf("%lld\n", sum);
	}
}









In    Python3  :






def z(w, T):
    T.append(len(w))
    l = r = 0
    for i in range(1, len(w)):
        k = 0
        if i < r:
            k = min(r-i, T[i-l])
        while i+k<len(w) and w[i+k] == w[k]:
            k += 1
        T.append(k)
        if i+k > r:
            l = i
            r = i+k

N = int(input())
for i in range(N):
    curr = input()
    count = 0
    T = []
    z(curr, T)
    for j in range(len(T)):
        count += T[j]
    print(count)