Pagini recente » Cod sursa (job #1693447) | Cod sursa (job #2030669) | Cod sursa (job #2234708) | Cod sursa (job #1949224) | Cod sursa (job #3212224)
// ConsoleApplication2.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <fstream>
#include <vector>
#include <string>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string A, B;
int pos;
vector <int> app;
int kmp[1001];
int main() {
cin >> A >> B;
for (int i = 1; i < A.size(); i++)
{
int j= kmp[i - 1];
while (j > 0 && A[i] != A[j])
j = kmp[j - 1];
if (A[i] == A[j])
{
j++;
kmp[i] = j;
}
}
for (int i = 0; i < B.size(); i++)
{
while (pos > 0 && B[i] != A[pos])
{
pos = kmp[pos - 1];
}
if (B[i] == A[pos])
{
pos++;
if (pos == A.size())
{
app.push_back(i - A.size() + 1);
pos = kmp[pos - 1];
}
}
}
cout << app.size() << "\n";
for(int i=0;i<min((int)app.size(),1000);i++)
cout << app[i] << " ";
return 0;
}