Pagini recente » Cod sursa (job #2246205) | Cod sursa (job #78591) | Cod sursa (job #2196487) | Cod sursa (job #2577919) | Cod sursa (job #2405529)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMAX=2000005;
char A[NMAX],B[NMAX];
int pos[1050],pi[NMAX];
int N=0,M=0,k=0,nr=0;
void prefix()
{
pi[1]=0;
k=0;
for (int i=2; i<=M; i++)
{
while (k&&A[k+1]!=A[i])
k=pi[k];
if (A[k+1]==A[i])
k++;
pi[i]=k;
}
}
void kmp()
{
k=0;
for (int i=1; i<=N; i++)
{
while (k&&A[k+1]!=B[i])
k=pi[k];
if (A[k+1]==B[i])
++k;
if (k==M)
{
k=pi[M];
++nr;
if (nr<=1000)
pos[nr]=i-M;
}
}
}
int main()
{
ios_base::sync_with_stdio(true);
fin.getline(A,sizeof(A));
fin.getline(B,sizeof(B));
for (;(A[M]>='A'&&A[M]<='Z')||(A[M]>='a'&&A[M]<='z')||(A[M]>='0'&&A[M]<='9'); M++);
for (;(B[N]>='A'&&B[N]<='Z')||(B[N]>='a'&&B[N]<='z')||(B[N]>='0'&&B[N]<='9'); N++);
for (int i=M; i; i--)
A[i]=A[i-1];
A[0]=' ';
for (int i=N; i; i--)
B[i]=B[i-1];
B[0]=' ';
prefix();
kmp();
fout<<nr<<"\n";
for (int i=1; i<=min(nr,1000); i++)
fout<<pos[i]<<" ";
return 0;
}