Cod sursa(job #1745629)

Utilizator dani_mocanuDani Mocanu dani_mocanu Data 22 august 2016 13:00:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int nmax = 2000005;
int N,M,pi[nmax],fans;
char a[nmax],b[nmax];
vector < int > ans;

inline void Pi()
{
    int i,k;
    k = 0;
    pi[1] = 0;
    for(i = 2; i <= N; i++)
    {
        while(k && a[k+1] != a[i]) k = pi[k];
        if(a[k+1] == a[i]) k++;
        pi[i] = k;
    }
}

int main()
{
    int i,k = 0;
    fin >> (a+1) >> (b+1);
    N = strlen(a+1), M = strlen(b+1);
    Pi();
    for(i = 1; i <= M; i++)
    {
        while(k && a[k+1] != b[i]) k = pi[k];
        if(a[k+1] == b[i]) k++;
        if(k == N && fans < 1000) ans.push_back(i - N), fans++;
        else if(k == N) fans++;

    }
    fout << fans << "\n";
    for(i = 0; i < ans.size(); ++i)
        fout << ans[i] << " ";
    fout.close();
    return 0;
}