Pagini recente » Cod sursa (job #1135438) | Cod sursa (job #2210666) | Cod sursa (job #2106090) | Cod sursa (job #2260735) | Cod sursa (job #2130972)
#include <fstream>
#include <cstring>
using namespace std;
char v[2000002],w[2000002];
int pref[2000002],poz[1002],n,m,c=0;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
void cstr()
{
int j=0;
for(int i=2;i<=n;i++)
{
while(v[j+1]!=v[i]&&j>0)
{
j=pref[j];
}
if(v[j+1]==v[i])
{
j++;
}
pref[i]=j;
}
}
void cauta()
{
int j=0;
for(int i=1;i<=m;i++)
{
while(v[j+1]!=w[i]&&j>0)
{
j=pref[j];
}
if(v[j+1]==w[i])
j++;
if(j==n)
{
c++;
if(c<=1000)
poz[c]=i-n;
j=pref[j];
}
}
}
int main()
{
f>>v+1;
f>>w+1;
n=strlen(v+1);
m=strlen(w+1);
cstr();
cauta();
g<<c<<"\n";
if(c<=1000)
{
for(int i=1;i<=c;i++)
{
g<<poz[i]<<" ";
}
}
else
{
for(int i=1;i<=1000;i++)
{
g<<poz[i]<<" ";
}
}
return 0;
}