Cod sursa(job #1360821)

Utilizator zpaePopescu Andreea zpae Data 25 februarie 2015 18:10:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <string>
using namespace std;
#define N 2000005

int n,m,u[N];
string a, b;

void prefix()
{
    int i,q=0;
    for(i=2;i<=m;i++)
    {
        while(q&&a[q+1]!=a[i])
            q=u[q];
        if(a[q+1]==a[i])
            q++;
        u[i]=q;
    }
}

int main()
{
    ifstream in ("strmatch.in");
    ofstream out ("strmatch.out");
    int i,q=0,k=0,p[1005];
    getline(in,a);
    getline(in,b);
    a='.'+a;
    b=','+b;
    m=a.length()-1;
    n=b.length()-1;
    prefix();
    for(i=1;i<=n;i++)
    {
        while(q&&a[q+1]!=b[i])
            q=u[q];
        if(a[q+1]==b[i])
            q++;
        if(q==m)
        {
            k++;
            if(k<=1000)
                p[k]=i-m;
            q=u[m];
        }
    }
    //out<<n<<' '<<m;
    out<<k<<endl;
    if(k>1000)
        k=1000;
    for(i=1;i<=k;i++)
        out<<p[i]<<' ';
    out<<endl;
    return 0;
}