Cod sursa(job #1316517)

Utilizator space.foldingAdrian Soucup space.folding Data 13 ianuarie 2015 21:28:49
Problema Potrivirea sirurilor Scor 36
Compilator cpp Status done
Runda Arhiva educationala Marime 1.75 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <sstream>
#include <deque>
#include <bitset>
#include <complex>
#include <functional>
#include <memory>
#include <numeric>
#define x first
#define y second
typedef std::pair<int, int> pii;
 
using namespace std;
 
 
 
int main () {
        ifstream fin("strmatch.in");
        ofstream fout("strmatch.out");
        static char s[2000007], g[2000007];
        fin.get(s, 2000007);
        fin.get();
        fin.get(g, 2000007);
        int n = strlen(s);
        int m = strlen(g);
        int k = 0;
        static int pi[2000007], please[2000007], volc = 0;
        long long meg = 0;
        pi[1] = 0;
        for(int i = 2; i < n; i++)
        {
                while(k > 0 && (s[k + 1]) != s[i])
                        k = pi[k];
                if(s[k + 1] == s[i])
                        k++;
                pi[i] = k;
        }
        int q = 0;
        for(int i = 1; i < m; i++)
        {
                while(q > 0 && (s[q + 1] != g[i]))
                        q = pi[q];
                if(s[q + 1] == g[i])
                        q++;
                if(q == n - 1)
                {
                        volc++;
                        please[meg++] = i - n + 1;
                }
        }
        {
                fout << volc << "\n";
                for(int i = 0; i < min(1000, volc); i++)
                        fout << please[i] << " ";
        }
        return 0;
}