Pagini recente » Cod sursa (job #19276) | Cod sursa (job #2329784) | Cod sursa (job #3317028) | Cod sursa (job #3315529) | Cod sursa (job #3320733)
#include <bits/stdc++.h>
using namespace std;
char s[2000005], T[2000005];
int LPS[2000005], Sol[2000005], nr;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
void PS(char s[])
{
int m=strlen(s);
int lg = 0;
int i = 1;
while (i<m)
{
if (s[i]==s[lg])
{
lg++;
LPS[i] = lg;
i++;
}
else if (lg) lg = LPS[lg - 1];
else
{
LPS[i] = 0;
i++;
}
}
}
void KMP(char T[], char S[])
{
int N = strlen(T);
int M = strlen(S);
PS(S);
int i=0;
int lg=0;
while (i<N)
{
if (T[i]==S[lg])
{
i++;
lg++;
if (lg == M)
{
Sol[++nr] = i-lg;
lg = LPS[lg-1];
}
}
else if(i<N && T[i] != S[lg])
if (lg) lg = LPS[lg-1];
else i++;
else i++;
}
}
int main()
{
fin >> s>> T;
KMP(T,s);
fout <<nr<<'\n';
for (int i=1; i<=nr; i++) fout << Sol[i] <<" ";
fout <<"\n";
return 0;
}