Cod sursa(job #1648447)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 11 martie 2016 10:13:11
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define w 2000001
using namespace std;
char s1[w];char s2[w];
int n,m;
unsigned int pi[w];
vector <unsigned int> v;
void prefix()
{
    pi[1]=0;int k=0,q;
    for (q=2;q<=n;q++)
    {
        while ( k>0 && s1[k+1]!=s1[q] )
            k=pi[k];
        if (s1[k+1]==s1[q])k++;
        pi[q]=k;
    }
}
int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    char r[w];
    f.get(s1,w,'\n');f.get();
    f.get(s2,w,'\n');f.get();
    n=strlen(s1);m=strlen(s2);
    strcpy(r,s1);strcpy(s1+1,r);s1[0]='\0';
    strcpy(r,s2);strcpy(s2+1,r);s2[0]='\0';
    prefix();
    unsigned int q,k=0;
    for (q=1;q<=m;q++)
    {
        while (k>0 && s1[k+1]!=s2[q])
            k=pi[k];
        if (s1[k+1]==s2[q]) k++;
        if (k==n)
        {
            v.push_back(q-n);
            k=pi[k];
        }
    }
    n=v.size();
    g<<n<<'\n';
    n=min(n,1000);
    for (k=0;k<n;k++)
        g<<v[k]<<' ';
    g<<'\n';
    f.close();
    g.close();
    return 0;
}