Cod sursa(job #2445935)
| Utilizator | Data | 6 august 2019 11:25:51 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.59 kb |
#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;
}
