Pagini recente » Cod sursa (job #1335651) | Cod sursa (job #416088) | Cod sursa (job #2845294) | Cod sursa (job #20877) | Cod sursa (job #2339090)
#include <fstream>
using namespace std;
#define FILENAME "strmatch"
ifstream fin (FILENAME".in");
ofstream fout(FILENAME".out");
const int MAXLEN = 2000000 + 16;
const int MAXSOL = 1000 + 16;
char Pattern[MAXLEN], Text[MAXLEN];
int Sol[MAXSOL], PSfix[MAXLEN];
int N, M, Count;
int main()
{
fin >> (Pattern+1);
fin >> (Text+1);
int K;
/// Precalculare prefix/sufix KMP
PSfix[1] = 0;
for(N = 2; Pattern[N]; ++N)
{
K = PSfix[N-1];
while(K > 0 && Pattern[K+1] != Pattern[N])
K = PSfix[K];
if(Pattern[K+1] == Pattern[N])
++K;
PSfix[N] = K;
}
--N;
K = 0;
for(M = 1; Text[M]; ++M)
{
while(K > 0 && Pattern[K+1] != Text[M])
K = PSfix[K];
if(Pattern[K+1] == Text[M])
++K;
if(K == N)
{
++Count;
if(Count <= 1000)
Sol[Count] = M - N;
K = PSfix[K];
}
}
--M;
fout << Count << '\n';
if(Count > 1000)
Count = 1000;
for(int i = 1; i <= Count; ++i)
fout << Sol[i] << ' ';
return 0;
}