Cod sursa(job #2100972)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 6 ianuarie 2018 17:33:01
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
const int NMAX=1e5+5;
string A,B;
int n,h,k,S[NMAX];
vector <int> sol;
int main()
{
    fi>>A;
    fi>>B;
    n=A.size();
    h=B.size();
    A="#"+A;
    B="#"+B;
    S[0]=-1;
    S[1]=0;
    k=0;
    for(int i=2;i<=n;i++)
    {
        while(k>0 && A[i]!=A[k+1])
            k=S[k];
        if(A[i]==A[k+1])
            k++;
        S[i]=k;
    }
    k=0;
    for(int i=1;i<=h;i++)
    {
        while(k>0 && B[i]!=A[k+1])
            k=S[k];
        if(B[i]==A[k+1])
            k++;
        if(k==n)
        {
            sol.push_back(i-k);
            k=S[k];
        }
    }
    fo<<sol.size()<<"\n";
    if(sol.size()>1000)
        n=1000;
    else
        n=sol.size();
    for(int i=0;i<n;i++)
        fo<<sol[i]<<" ";
    fi.close();
    fo.close();
    return 0;
}