Pagini recente » Cod sursa (job #129178) | Cod sursa (job #1951831) | Cod sursa (job #2496876) | Cod sursa (job #1961087) | Cod sursa (job #1092181)
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 2000010;
int N, M, Z[NMAX], MatchCnt;
char Pattern[NMAX], Text[NMAX];
vector<int> MatchPos;
void BuildZ()
{
Z[1] = 0;
for(int i = 2, C = 1, Right = 1; i <= N; ++ i)
{
if(Right >= i) Z[i] = min(Right - i + 1, Z[i - C + 1]);
for(; i + Z[i] <= N && Pattern[Z[i] + 1] == Pattern[i + Z[i]]; ++ Z[i]);
if(i + Z[i] - 1 > Right)
{
C = i;
Right = i + Z[i] - 1;
}
}
}
void Z_Algorithm()
{
BuildZ();
for(int i = 1, C = 0, Right = 0; i <= M; ++ i)
{
int LCP = 0;
if(Right >= i) LCP = min(Right - i + 1, Z[i - C + 1]);
for(; LCP < N && i + LCP <= M && Pattern[LCP + 1] == Text[i + LCP]; ++ LCP);
if(i + LCP - 1 > Right)
{
C = i;
Right = i + LCP - 1;
}
if(LCP == N)
{
MatchCnt ++;
if(MatchCnt <= 1000) MatchPos.push_back(i - 1);
}
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(Pattern + 1); N = strlen(Pattern + 1);
gets(Text + 1); M = strlen(Text + 1);
Z_Algorithm();
printf("%i\n", MatchCnt);
for(int i = 0; i < MatchPos.size(); ++ i) printf("%i ", MatchPos[i]);
}