Cod sursa(job #864166)
| Utilizator | Data | 24 ianuarie 2013 18:31:29 | |
|---|---|---|---|
| Problema | Potrivirea sirurilor | Scor | 18 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.54 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n,m,k,p,v,sol[1002],pi[2000002],i;
char a[2000002],b[2000002];
int main ()
{
f.get(a,2000002);
f.get();
f.get(b,2000002);
for (n=0;a[n];n++);
for (m=0;b[m];m++);
for (i=2;i<=m;i++)
{
while (k>0 && a[k+1]!=b[i])
k=pi[k];
if (a[k+1]==b[i])
k++;
pi[i]=k;
if (k>=n-1)
{
p++;
sol[p]=i-n+1;
if (p>1000)
break;
}
}
g<<p<<'\n';
for (i=1;i<=p;i++)
g<<sol[i]<<" ";
}