Pagini recente » Cod sursa (job #1510066) | Cod sursa (job #2969073) | Cod sursa (job #773) | Cod sursa (job #792464) | Cod sursa (job #2865090)
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[2000011],a[2000011];
int lps[2000011],i,j,n,m,S;
vector <int> sol;
void lpsbuild()
{
int i=1,j=0;
while(i<m)
{
if(a[i]==a[j])
{
j++;
lps[i]=j;
i++;
}
else
if(j==0)
{
lps[i]=0;
i++;
}
else
j=lps[j-1];
}
}
void kmp()
{
int i=0,j=0;
while(i<n)
{
if(A[i]==a[j])
{
i++;
j++;
if(j==m)
{
S++;
if(S<=1000)
sol.push_back(i-m);
j=lps[j-1];
}
}
else
if(j==0)
i++;
else
j=lps[j-1];
}
}
int main()
{
f>>a;
f>>A;
m=strlen(a);
n=strlen(A);
lpsbuild();
kmp();
g<<S<<'\n';
for(i=0;i<sol.size();i++)
g<<sol[i]<<" ";
return 0;
}