Pagini recente » Cod sursa (job #1905765) | Cod sursa (job #1006195) | Cod sursa (job #3141181) | Cod sursa (job #2716177) | Cod sursa (job #1316138)
#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[2000001], g[2000001];
fin.get(s, 2000001);
fin.get();
fin.get(g, 2000001);
int n = strlen(s);
int m = strlen(g);
int k = 0;
int pi[20000], please[20000], 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)
{
cout << volc << "\n";
for(int i = 0; i < 1000; i++)
cout << please[i] << " ";
}
else
{
cout << volc << "\n";
for(int i = 0; i < volc; i++)
cout << please[i] << " ";
}
return 0;
}