Pagini recente » Cod sursa (job #2855866) | Cod sursa (job #2029083) | Cod sursa (job #1229157) | Cod sursa (job #804018) | Cod sursa (job #1316475)
#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");
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;
int pi[200000], please[200000], 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;
}
}
if(volc >= 1000)
{
fout << volc << "\n";
for(int i = 0; i < 1000; i++)
fout << please[i] << " ";
}
else
{
fout << volc << "\n";
for(int i = 0; i < volc; i++)
fout << please[i] << " ";
}
return 0;
}