Pagini recente » Autentificare | Cod sursa (job #1588976) | Cod sursa (job #1732066) | Cod sursa (job #1236739) | Cod sursa (job #2307046)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int L=2000001;
int sol[1001], lps[L+1];
char txt[L+1], pat[L+1];
int Nsol, n, m;
void LPS(char *pat, int m)
{
/// Calculez LPS
int len=0;
lps[0]=0;
int i=1;
while(i<m)
{
if(pat[i]==pat[len])
{
++len;
lps[i]=len;
++i;
}
else /// pat[i]!=pat[len]
{
if(len!=0) len=lps[len-1];
else
{
lps[i]=0;
++i;
}
}
}
}
void KMP_search(char *txt, char *pat)
{
n=strlen(txt);
m=strlen(pat);
LPS(pat, n);
int i=0, j=0;
while(i<n)
{
if(txt[i]==pat[j])
{
++j;
++i;
}
if(j==m)
{
++Nsol;
if(Nsol<=1000) sol[Nsol]=i-j;
j=lps[j-1];
}
else if(i<n && pat[j]!=txt[i])
{
if(j!=0) j=lps[j-1];
else ++i;
}
}
}
int main()
{
fin.getline(pat, L);
fin.getline(txt, L);
Nsol=0;
KMP_search(txt, pat);
fout<<Nsol<<"\n";
for(int i=1; i<=min(Nsol, 1000); ++i) fout<<sol[i]<<" ";
fout<<"\n";
return 0;
}