Cod sursa(job #1833073)
| Utilizator | Data | 21 decembrie 2016 16:44:03 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 1.07 kb |
#include <fstream>
#include <string.h>
using namespace std;
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[20001],b[20001];
int urm[20000],i,j,m,n,c=0,v[1000];
in>>a>>b;
m=strlen(a);
n=strlen(b);
urm[0]=-1;
j=-1;
for(i=1;i<m;i++)
{
while(j>-1 && a[j+1]!=a[i])
{
j=urm[j];
}
if(a[j+1]==a[i])
{
j++;
}
urm[i]=j;
}
j=-1;
for(i=0;i<n;i++)
{
while(j>-1 && a[j+1]!=b[i])
{
j=urm[j];
}
if(a[j+1]==b[i])
{
j++;
}
if(j==m-1)
{
if(c<1000)
v[c]=i-m+1;
c++;
}
}
out<<c<<"\n";
for(i=0;i<c;i++)
{
out<<v[i]<<" ";
}
return 0;
}
