Cod sursa(job #2366713)
| Utilizator | Data | 4 martie 2019 21:45:35 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 40 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 1.29 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N=1000009,K=1009;
int m,k;
int f[N],sol[K];
char pattern[N];
void build_failure()
{
f[0]=f[1]=0;
for(int i=1; i<m; i++)
{
int j=f[i];
for(;;)
{
if(pattern[j]==pattern[i])
{
f[i+1]=j+1;
break;
}
if(j==0)
{
f[i+1]=0;
break;
}
j=f[j];
}
}
}
void solve()
{
build_failure();
char text;
int i=0,j=0;
while(fin>>text)
{
i++;
int stg=0;
while(stg==0)
{
if(text==pattern[j])
{
j++;
if(j==m)
sol[++k]=i-m;
if(k==1000)
return;
stg=1;
}
else
{
if(j!=0)
j=f[j];
else
stg=1;
}
}
}
}
int main()
{
fin>>pattern;
m=strlen(pattern);
solve();
fout<<k<<'\n';
for(int i=1;i<=k;i++)
fout<<sol[i]<<" ";
return 0;
}
