Cod sursa(job #2112855)

Utilizator malina2109Malina Diaconescu malina2109 Data 23 ianuarie 2018 22:15:57
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string a,b;
vector<int> sol;
int urm[2000000];
int n,m;
void urma()
{
    int k=-1;
    urm[0]=0;
    for(int x=1;x<m;x++)
    {
        while(k>0 && a[k+1]!=a[k]) k=urm[k];
        if(a[k+1]==a[k]) k++;
        urm[x]=k;
    }
}
int main()
{
    int x=-1;
    f>>a;
    f>>b;
    n=b.length();
    m=a.length();
   // n=strlen(b);
   // m=strlen(a);
    urma();
    for(int i=0;i<n;i++)
    {
        while(x>0&&a[x+1]!=b[i]) x=urm[x];
        if(a[x+1]==b[i]) x++;
        if(x==m-1)
        {x=urm[m];
        if(sol.size()<1000)
            sol.push_back(i-m+1);
        }
    }
    g<<sol.size()<<"\n";
    for(int i=0;i<sol.size();i++)
        g<<sol[i]<<" ";
    return 0;
}