先将\(S\)后再接一个\(S\)，也就是原\(S\)的任意一个位置都可以作为左端点开始匹配
令\(t_0\)匹配的位置为\(x\)，则\(t_i\)匹配的位置是\(x+i\)，\(s_{x+i}=(ai+ax+b)~mod~n\)，然后这样就对\(a_x\)有限制了
\(0\equiv mod~2,1\equiv mod~2\)分开讨论，然后每个限制是一个区间，所有的\(i\)全部并起来
因为\((a,n)=1\)，所以有唯一位置
再考虑\(S\)末端有一些位置不够匹配，这部分可以kmp匹配一下减去
原文：https://www.cnblogs.com/Grice/p/12833016.html