Pagini recente » Cod sursa (job #710515) | Cod sursa (job #2633355) | Cod sursa (job #1413932) | Cod sursa (job #1363456) | Cod sursa (job #2445934)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char ch,a[2000005],b[2000005];
int pi[2000005],pi2[2000005],i,j,nr1,nr2,nr, nrafis;
int main()
{
while(f.get(ch))
{
if(ch=='\n')
break;
a[++nr1]=ch;
}
while(f.get(ch))
{
if(ch=='\n')
break;
b[++nr2]=ch;
}
pi[1]=0;
j=1;
for(i=2; i<=nr1; i++)
{
if(a[i]==a[j])
{
pi[i]=j;
j++;
}
else while(j!=1)
{
j=pi[j-1]+1;
if(a[i]==a[j]){
pi[i]=j;
j++;
break;
}
}
}
pi2[1]=0;
j=1;
for(i=1; i<=nr2; i++)
{
if(b[i]==a[j])
{
pi2[i]=j;
j++;
}
else while(j!=1)
{
j=pi[j-1]+1;
if(b[i]==a[j]){
pi2[i]=j;
j++;
break;
}
}
}
for(i=1; i<=nr2; i++)
if(pi2[i]==nr1)
nr++;
g<<nr<<'\n';
if(nr<=1000)
for(i=1; i<=nr2; i++)
if(pi2[i]==nr1)
g<<i-nr1<<' ';
else
{
for(i=1; i<=nr2 && nrafis<1000; i++)
if(pi2[i]==nr1)
{
g<<i-nr1<<' ';
nrafis++;
}
}
return 0;
}